[백준] 2437번 저울 자바

문제

 

2437번: 저울

 

 

문제 풀이

 

구글링해서 풀었다. 논리 생각하기가 어려웠던 것 같다.

문제 예시로 알고리즘을 설명해보자면 우선 주어진 배열 [3, 1, 6 2, 7, 30, 1]을 정렬한다. → 작은 수부터 만들 수 있는 숫자를 찾기 위해서 

 

정렬된 배열 A = [1, 1, 2, 3, 6, 7, 30], 배열 B를 A로 만들 수 있는 숫자 배열이라고 들겠다.

A를 처음부터 반복하면서 B배열을 확인해보면

A[0]: 1로 만들 수 있는 숫자 B= {1}

A[1]: 1 추가로 만들 수 있는 숫자 B= {1, 2}

A[2]: 2 추가로 만들 수 있는 숫자 B= {1, 2, 3, 4}

A[3]: 3 추가로 만들 수 있는 숫자 B= {1, 2, 3, 4, 5, 6, 7}

A[4]: 6 추가로 만들 수 있는 숫자 B= {1, 2, 3, 4, 5, 6, 7, 8, .. 13}

A[5]: 7 추가로 만들 수 있는 숫자 B= {1, 2, 3, ... 20}

A[6]: 30추가로 만들 수 있는 숫자 B= {1, 2, 3, ... 20, 31, 32, 33, .. 50}

 

위처럼 B배열은1부터 순차적으로 숫자를 만들 수 있어야 한다. 왜냐하면 순차적이지 않으면 그 숫자가 바로 만들지 못하는 최소 숫자가 되기 때문이다. 이렇게 순차적으로 증가하는 조건을 체크해야 하는데, B배열의 최대값을 확인하면 된다. 만약 B의 최대값보다 그다음 A배열 값이 작다면 B의 배열은 이미 1부터 순차적으로 증가하기 때문에 계속해서 순차적으로 B배열을 만들 수 있지만 그렇지 못하다면 비는 숫자 공간이 생긴다.

 

 

소스 코드

 

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int answer = 1;
		int N = sc.nextInt();
		int[] arr = new int[N];

		for(int i = 0; i < N; i++)
			arr[i] = sc.nextInt();

		Arrays.sort(arr);
		for(int i = 0; i < N; i++) {
			if(answer < arr[i])
				break;
			answer += arr[i];	//만들 수 있는 배열의 Max값 갱신해나가는 거
		}
		
		System.out.println(answer);
		sc.close();
	}

}