백준 1332번: 풀자

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

문제에 대한 흥미도가 주어지고 1번부터 시작해서 +1 혹은 +2 번의 문제를 풀어나갈 때, 가장 낮은 흥미도와 가장 큰 흥미도의 차이가 v 이상을 만족하는 문제의 갯수를 구해야 한다. n이 50 이하의 자연수이기 때문에 백트래킹, BFS 등으로는 풀 수 없다. 따라서 상태를 저장하는 DP를 적용해야 한다.

 

+1, +2라는 선택지에 대한 경로가 생기며 이에 대한 상태는 (min, max, count)로 표현하였다.

List<int[]>[] dp = new List[n];
for (int i = 0; i < n; i++) {
    dp[i] = new ArrayList<>();
}
dp[0].add(new int[]{board[0], board[0], 1});

 

 

이미 이전 상태의 상태의 최대, 최소 흥미도의 차이가 v 이상이라면 문제를 더 풀지 않고 다른 상태에서 경로를 찾는다. 또한, 의미 없는 경로라면 추가하지 않는다. i의 위치에 도달하는 상태들 중 min이 작거나 같으면서 max가 크거나 같고 count가 작거나 같은 다른 상태는 흥미도의 범위도 좁고 문제도 더 많이 풀은 의미 없는 경로이므로 제거하게 한다.

for (int i = 0; i < n; i++) {
    for (int[] state : dp[i]) {
        int lo = state[0], hi = state[1], cnt = state[2];
        
        if (hi - lo >= v) {
            answer = Math.min(answer, cnt);
            continue;
        }
        
        for (int step = 1; step <= 2; step++) {
            int j = i + step;
            if (j >= n) {
                continue;
            }
            int newLo = Math.min(lo, board[j]);
            int newHi = Math.max(hi, board[j]);
            int newCnt = cnt + 1;
            
            boolean dominated = false;
            for (int[] e : dp[j]) {
                if (e[0] <= newLo && e[1] >= newHi && e[2] <= newCnt) {
                    dominated = true;
                    break;
                }
            }
            if (!dominated) {
                dp[j].removeIf(e -> e[0] >= newLo && e[1] <= newHi && e[2] >= newCnt);
                dp[j].add(new int[]{newLo, newHi, newCnt});
            }
        }
    }
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class 풀자1332 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
        int[] board = new int[n];
        st = new StringTokenizer(br.readLine());
        int min = 1000, max = 0;
        for (int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
            min = Math.min(board[i], min);
            max = Math.max(board[i], max);
        }
        br.close();
        if (max - min < v) {
            System.out.print(n);
            return;
        }
        
        List<int[]>[] dp = new List[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new ArrayList<>();
        }
        dp[0].add(new int[]{board[0], board[0], 1});
        
        int answer = n;
        
        for (int i = 0; i < n; i++) {
            for (int[] state : dp[i]) {
                int lo = state[0], hi = state[1], cnt = state[2];
                
                if (hi - lo >= v) {
                    answer = Math.min(answer, cnt);
                    continue;
                }
                
                for (int step = 1; step <= 2; step++) {
                    int j = i + step;
                    if (j >= n) {
                        continue;
                    }
                    int newLo = Math.min(lo, board[j]);
                    int newHi = Math.max(hi, board[j]);
                    int newCnt = cnt + 1;
                    
                    boolean dominated = false;
                    for (int[] e : dp[j]) {
                        if (e[0] <= newLo && e[1] >= newHi && e[2] <= newCnt) {
                            dominated = true;
                            break;
                        }
                    }
                    if (!dominated) {
                        dp[j].removeIf(e -> e[0] >= newLo && e[1] <= newHi && e[2] >= newCnt);
                        dp[j].add(new int[]{newLo, newHi, newCnt});
                    }
                }
            }
        }
        
        System.out.print(answer);
    }
}