🔗 Problem

https://www.acmicpc.net/problem/2437

👩‍💻 Code

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

// 저울

public class BJ2437 {
	
	static int n;
	static int total = 1;		// 최소 추의 무게인 1로 초기화
	static int[] weight;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		weight = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			weight[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(weight);
		
		for(int i = 0; i < weight.length; i++) {
			
			if(total < weight[i]) break;
			total += weight[i];
		}
		
		
		System.out.println(total);
	
	}

}

📌 Note

아이디어

• 오름차순 정렬 후, 1부터 측정할 수 있는 추의 무게를 찾아간다.
• weight[i]를 total에 더하면, i번째까지는 1~total 무게까지 측정할 수 있다.
• weight[i-1]과 weight[i] 사이의 무게는 total 보다 작기 때문에 측정 가능한 것.
• 만약 total < weight[i]라면, weight[i-1]과 weight[i] 사이의 무게를 만들 수 없기에 for문을 탈출한다.

틀렸습니다

• 처음에 total 대신 만들 수 있는 최대 무게를 max로 두고, 정렬 후 각 추의 조합으로 측정할 수 있는 무게를 Bit Mask를 사용하여 구현하였다.
• 베이스 로직은 위 풀이와 같은데 왜 틀렸는지 아직 해결하지 못했다.. (22.04.30 기준)

  해결 😍 (22.05.01)
  Bit Mask 사용 시 Math.pow(2, n)번 for문을 돌려야 하는데
  n은 최대 1000이므로 불가능하다.
  (질문 게시판을 통해 답변 받음)
  조건까지 꼼꼼하게 따져서 생각하고 풀자..!

• 어려운 문제는 아니었는데 결국 풀이를 참고하여 풀었다.