1026, 1037, 1085 - 보물, 약수, 직사각형에서 탈출

1026

보물

• N, A배열(N개의 수), B배열(N개의 수) 입력
• A배열을 재정렬하여 A 각 인덱스와 B 각 인덱스를 곱하여 모두 더함.
• 그 값이 최소가 되도록 재정렬했을 때, 그 최솟값을 출력.

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class bj1026_0125 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		Integer[] B = new Integer[N];

		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		for (int i = 0; i < N; i++) {
			B[i] = sc.nextInt();
		}
		sc.close();
		Arrays.sort(A);
		Arrays.sort(B, Collections.reverseOrder());
		int sum = 0;
		for (int i = 0; i < N; i++) {
			sum += (A[i] * B[i]);
		}
		System.out.println(sum);
	}
}

• A배열을 재정렬 할 필요가 없다는 게 이 코드의 핵심이다.
• A는 오름차순, B는 내림차순으로 정렬하고 각 인덱스끼리 곱해주면 된다.

 

1037

약수

• 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다.
• 어떤 수 N의 진짜 약수가 모두 주어질 때 N을 출력.

import java.util.Scanner;

public class bj1037_0125 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		int min = 1000000;
		int max = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
			min = (arr[i] < min) ? arr[i] : min;
			max = (arr[i] > max) ? arr[i] : max;
		}
		System.out.println(min * max);

	}
}

• 규칙을 좀 생각해보면 직감적으로 답을 알 것 같은 느낌인데, 그걸 증명하기는 어려울 것 같은 느낌이 들어서, 그냥 내 생각대로 작성해서 제출해봤더니 정답이 됐다.
• 그리고 역으로 그 규칙을 증명해보자면...
• 일단 그 규칙은, 입력 받은 수 중 가장 작은 수와 가장 큰 수를 곱하면 답이라는 거고
• 그럴 수 밖에 없는 이유는, 사실 잘 생각해보면 당연하다... 어떤 아주 큰 수의 모든 진짜 약수를 나열해보라고 한다면, 가장 작은 약수가 있을 것이고, 가장 큰 약수가 있을 것인데, 원래 수를 가장 작은 약수로 나눈 몫이 바로 가장 큰 약수가 되는 건 당연하니까...

 

1085

직사각형에서 탈출

• 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.

import java.util.Scanner;

public class bj1085_0125 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = new int[4];
		for (int i = 0; i < 4; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();

		int min1 = ((arr[2] - arr[0]) < arr[0]) ? (arr[2] - arr[0]) : arr[0];
		int min2 = ((arr[3] - arr[1]) < arr[1]) ? (arr[3] - arr[1]) : arr[1];
		System.out.printf("%d", min1 < min2 ? min1 : min2);

	}
}

• 그림을 상상해보면 쉽게 방법을 알 수 있다.
• 코드에 있는 수식 중 무조건 최소를 찾으면 답이다.