2437 저울(자바)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	
	static int N;
	static int number [];
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		number= new int [N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		
		for(int i=0; i<N; i++) {
			number[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(number);
		
		int minimum = solve();
		System.out.println(minimum);
	}
	
	public static int solve() {
		
		int result =0;
		int max = 0;
		if(number[0]!=1) {
			result = 1;
			return result;
			
		}else {
			max = 1;
			
		}
		
		
		for(int i=1; i<N; i++) {
			if(number[i] <= max +1 ) {
				max+= number[i];
			}else {
				result = max+1;
				return result;
				
			}
		}
		
		result = max+1;
		return result;
	}
}

 

 

우리는 주어진 저울추로

측정할 수 있는 무게를 

1 2 3 4 5 6 7 8 .. 이렇게 만드는 게 목적이다.

그러다가 만약 9 를 만들 수 없다!

그러면 주어진 저울추로 무게 9 를 측정할 수 없다는 거니깐,

9를 답으로 리턴하면 된다.

 

그러면, 1 2 3 4 5 6 7 .. 을 만들어보자.

 

1) 1 만들기

<1> 저울추 중에 1이 있으면 된다.

즉, 예시에 나오는 저울추 값들을 number 배열에 넣어서 이를 오름차순 할 예정인데,

이 때 맨 앞에 1이 없다면 무게 1을 측정할 수 없으므로 정답으로 1을 리턴하면 된다.

하지만, 맨 앞에 1이 있다면 그 다음 2를 만들면 된다.

 

2) 2 만들기 : 1 또는 2가 오면 된다.

<1> 1이 온다.

앞에서 저울추 1이 있다고 했으니, 여기에 만약 저울추 1이 또 있다면 더해서 2를 만들 수 있다.

존재하는 저울추 무게 : 1 1

측정 가능 무게 : 1 2(가능)

 

<2> 2가 온다.

존재하는 저울추 무게 : 1 2

측정 가능 무게 : 1 2(가능) 3

 

3) 3 만들기 

앞의 2 만들기 <1> 에서 1이 온 경우, 측정 가능 무게가 1 2 까지였다.

그럼 이제 3을 만들어야 한다.

 

<1> 1이 온다.

존재하는 저울추 무게 : 1 1 1 

측정 가능 무게 : 1 2 3(가능)

 

<2> 2가 온다.

존재하는 저울추 무게 : 1 1 2

측정 가능 무게 : 1 2 3(가능) 4 

 

<3> 3이 온다.

존재하는 저울추 무게 : 1 1 3

측정 가능 무게 : 1 2 3(가능) 4 5

 

<4> 만약 4가 왔다.

이 경우는 안된다.

 

존재하는 저울추 무게 : 1 1 4

측정 가능 무게 : 1 2 4 5 6 

 

3이 되는 건 절대 불가하다.

 

규칙을 찾아보면,

존재하는 저울추 무게 : 1 1 

측정 가능 무게 : 1 2 

인 상태에서, 다음으로 측정 가능 무게 3을 만들어야 하는데,

이 때 올 수 있는 저울추 무게는 3보다 작거나 같은 값이 와야 한다는 것이다.

 

즉, 

지금까지 만든 최댓값 + 1 (위의 경우 3) 보다 작거나 같은 값이 배열에서 나와야만 하고,

그렇지 않다면 1 2 3 4 5 6 .. 이렇게 만드는게 불가하다.

그래서 이렇게 불가한 경우는, 지금까지 만든 최댓값 + 1 을 정답으로 리턴하면 된다.

문제에서 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력하라고 했기 때문이다.

 

# 주의점

내가 아직 return 에 익숙하지 않아서 글로 남기는데,

solve 메서드에 보면 

		if(number[0]!=1) {
			result = 1;
			return result;
			
		}

여기서 return 을 사용한 경우를 볼 수 있다.

즉 number[0] 이 1 이 아니면 result 에 1을 담아서 return 하라고 되어 있는데,

이렇게 return 하고 나면 solve 메서드의 아래 코드 부분이 실행되지 않고 끝이 난다.

그리고 result 에는 1 이 담긴 상태가 된다.

 

참고 자료 : 

https://plplim.tistory.com/59

[백준 #2437번 JAVA] 저울 풀이