https://www.acmicpc.net/problem/2437
백준 골드2 난이도의 문제로, 오랜만에 문제 풀면서 머리를 좀 많이 쓴 문제가 아니었나 싶다.
우선 문제를 보면, 배낭 문제와 비슷한 형태를 띄고 있다.
그래서 일단 그리디 문제라는 것은 어느 정도 유추가 가능했다.
문제를 풀기 위해 조건을 좀 찾아봤다.
예시 1
우선 문제 풀면서 메모장에 적어놨던 첫번째 예시를 가져왔다.
an은 무게 추가 정렬되었을 때 n번째 추를 의미하고, SN은 n번째 무게추까지의 누적 무게 합을 의미하고, 그 옆은 부분 집합을 의미한다.
위의 예시에서는 무게추가 순서대로 1,2,4,9인 순서대로 확인한다.
무게 추를 추가할때마다 누적합과 부분 집합에 해당되는 값들을 확인하면, 다음을 알 수 있다.
an > S(N-1) + 1 일때, S(N-1)+1 이 측정할 수 없는 최소 무게가 된다.
이를 확인하기 위해, 문제에서 주어진 예시로도 한 번 더 검증을 했다.
예시 2
문제 예시에서 주어진 추를 정렬하면 1,1,2,3,6,7,30 순이 된다.
순차적으로 누적합 연산을 하면서, 위에서 말한 an > S(N-1) + 1 일때가 나타나는 지를 확인했다.
무게가 30인 추가 추가될 경우, 무게 합산 중 21이 측정이 불가능하며, 예제 출력 값과 같은 21이 답이 된다.
이러한 규칙을 찾고, 해당 방식을 기반으로 코드를 구현하여 제출했지만, 틀렸다고 나왔다.
어느 부분을 놓쳤을까 고민하던 중, 한 가지 빠트린 경우가 있었다.
위의 로직대로만 구현할 경우 추를 다 쓸 때까지 모든 무게가 측정 가능하다면,
모든 추의 무게 합산 값 + 1 이 측정 불가능한 최소값이 된다.
해당 부분을 처리하기 위한 부분을 추가해주었더니 맞았다.
import java.io.*;
import java.util.*;
public class boj2437 {
static int N, result;
static int prefixSum[];
static int pendulum[];
public static void Greedy() {
// 가장 가벼운 추가 1보다 클 경우 무게 1 측정 불가
if (pendulum[1] != 1) {
result = 1;
return;
}
prefixSum[1] = pendulum[1];
int idx = 2;
while (idx <= N) {
if (pendulum[idx] > prefixSum[idx - 1] + 1) {
result = prefixSum[idx - 1] + 1;
return;
}
prefixSum[idx] = prefixSum[idx - 1] + pendulum[idx];
idx++;
}
result = prefixSum[idx - 1] + 1;
}
public static void pre() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
prefixSum = new int[N + 1];
pendulum = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
pendulum[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(pendulum);
}
public static void main(String args[]) throws IOException {
pre();
Greedy();
System.out.println(result);
}
}
해당 코드의 실행 시간은 다음과 같다.
처음 실패 두 번은 모든 추의 무게를 다 합친 것을 초과해서 측정이 불가능할 때를 고려 못해서 발생했다.