[코드트리] 9 - DP, 구간합 DP

문제 - 파일 합치기

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-Combine-2-3/description

2개씩 합치기 3 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        int N = read();
        int[] pSum = new int[N+1];
        int[][] dp = new int[N+1][N+1];
        for(int i = 0; i<=N; i++){
            Arrays.fill(dp[i], INF);
        }
        int[] cost = new int[N+1];
        for(int i=1; i<=N; i++){
            cost[i] = read();
            pSum[i] = pSum[i-1] + cost[i];
            dp[i][i] = 0;
        }

        for(int len = 2; len <=N; len++){
            for(int i = 1; i + len - 1<=N; i++){
                int j = i + len - 1;
                for(int k = i; k<j; k++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + pSum[j] - pSum[i-1]);
                }
            }
        }
        System.out.print(dp[1][N]);
    }
}

사고의 흐름 및 풀이

초기값은 자기 자신 하나만 있으면 cost가 0이니까 dp[i][i] = 0

1개는 이미 초기화했으니 구간 크기 2부터 처리해야 하고 왼쪽 구간 오른쪽 구간으로 나눠서 보면

중간 지점을 k라 했을때, 문제 조건상 cost는 구간에 해당하는 모든 값의 sum이므로 

prefix sum을 이용하여 [i,j] 구간의 sum은 ps[j] - ps[i-1]이므로 

dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + pSum[j] - pSum[i-1]);

prefix sum 처리를 위해서 1-based index를 사용했으니

정답은 dp[1][N]

---

문제 - 팰린드롬과 삭제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-palindrome-and-remove/description

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();
        int N = s.length;
        int[][] dp = new int[N][N];
        for(int i = 0; i<N; i++)
            dp[i][i] = 1;
        
        for(int len = 2; len <= N; len++){
            for(int i= 0; i+len-1<N; i++){
                int j = i+len-1;
                if(s[i] == s[j]){
                    if(len == 2)
                        dp[i][j] = 2;
                    else
                        dp[i][j] = Math.max(dp[i][j], dp[i+1][j-1]+2);
                }
                else{
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        System.out.print(N - dp[0][N-1]);
    }
}

사고의 흐름 및 풀이

팰린드롬이란 반으로 갈랐을때 접두사와 접미사가 같은 문자열을 말함.

팰린드롬을 만들기 위해 문자열에서 최소 몇개의 문자를 삭제해야하는지를 구해야 하므로 

꼭 연속되어야할 필요가 없다. 따라서 이미 처리된 구간에서 팰린드롬의 최대 길이를 갱신해나가면 된다.

정답은 전체 문자의 갯수 - 현재 문자열에서 만들 수 있는 최대 팰린드롬의 길이가 된다.

DP 초기화 및 전이

자기 자신은 항상 팰린드롬이므로 dp[i][i] = 1이다.

구간 1은 이미 처리했으므로 구간 2부터 처리를 시작해야한다.

 

1) 만약 양쪽 끝이 문자가 같다면

안쪽이 팰린드롬이든 아니든 최대를 받아와서 길이를 +2 확장시켜줄수 있다. 

현재 구간 길이가 2라면 최초의 팰린드롬이므로 2이다.

그것보다 크다면 안쪽에서의 최대의 팰린드롬 값을 받아와서 +2를 한다.

->max(dp[ i ][ j ], dp[ i+1 ][ j-1 ]+2)

 

2) 만약 양쪽 끝의 문자가 다르다면

왼쪽과 오른쪽으로 나누어 둘중 최대의 값으로 취해야 한다. 

-> 왼쪽 : i ~ j-1, 오른쪽 : i+1 ~ j 로 잡고 둘중 큰 값으로 구간 i~j의 최대값으로 설정한다.

---

문제 - 좌우 대칭 문자열 찾기

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-longest-palindrome-4/description

가장 긴 좌우 대칭인 문자열 찾기 4 설명 | 코드트리

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();
        int N = s.length;

        // [i,j] 가 팰린드롬인가
        boolean[][] dp = new boolean[N][N];
        for(int i = 0; i<N; i++)
            dp[i][i] = true;

        int si = 0;
        int max = 1;
        for(int len = 2; len <=N; len++){
            for(int i = 0; i+len-1<N; i++){
                int j = i + len -1;
                if(s[i] == s[j]){
                    if(len == 2)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i+1][j-1];
                }
                else
                    continue;
                    
                if(dp[i][j] && len > max){
                    max = len;
                }
            }
        }
        System.out.print(max);
    }
}

사고의 흐름 및 풀이

이때 문제를 잘못읽어서 계속 문자열 자체를 출력하기를 시도했다..

연속으로 팰린드롬인 문자열의 최대 길이가 몇인지를 출력해야 한다. 

 

DP 초기화 및 전이

dp[i][i] = 자기 자신은 길이 1이므로 항상 팰린드롬, true.

연속이라는 조건이 있으므로 양쪽 끝의 문자가 같더라도 구간 길이가 2일때만 무조건 true이고 

나머지는 안쪽 구간의 boolean 값을 추종한다.

양쪽 끝의 문자가 다르면 그 구간은 그냥 놔둬도 된다. -> 초기값이 false이므로

한 구간의 처리가 끝날 때마다 최대 길이를 max에 갱신하고 필요하면 start index를 갱신한다.

---

문제 - 인접한 두 수의 차 (다시 풀기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-two-adjacent-numbers-and-difference/description

인접한 두 수와 차 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    public static void main(String[] args) throws IOException{
        int N = read();
        int[] arr = new int[N];
        for(int i = 0; i<N; i++){
            arr[i] = read();
        }

        int[][][] dp = new int[N][N][11];
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                Arrays.fill(dp[i][j], -1);
            }
        }

        for(int i = 0; i<N; i++){
            dp[i][i][arr[i]] = 0;
        }

        for(int len = 2; len <=N; len++){
            for(int i = 0; i+len-1<N; i++){
                int j = i+len-1;
                for(int k = i; k<j; k++){
                    for(int lv = 0; lv<=10; lv++){
                        if(dp[i][k][lv] == -1)
                            continue;
                        for(int rv = 0; rv <= 10; rv++){
                            if(dp[k+1][j][rv] == -1)
                                continue;
                            int nv = Math.abs(lv-rv);
                            dp[i][j][nv] = Math.max(dp[i][j][nv], dp[i][k][lv] + dp[k+1][j][rv] + lv + rv);
                        }
                    }
                }
            }
        }

        int ans = -1;
        for(int i = 0; i<=10; i++){
            ans = Math.max(ans, dp[0][N-1][i]);
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

평범한 구간합 dp처럼 2차원으로 설정하게 되면 문제 조건에서 점수는 두 수의 합으로 정해지고 새로 생기는 수는 두수의 차이므로 전에 풀었던 점수는 두 수의 차로 정해지고 새로 생기는 수는 두 수의 합인 경우에 prefix sum 전처리 배열을 활용하여 하는 것과는 다르게 상태가 부족하게 된다. 

-> 따라서 3차원 dp로 정의하고 문제 조건에서 N <= 200이고 값의 범위는 [1, 10] 이라 했으니 

가능한 수의 차의 범위는 [0, 10] 이다.

dp[i][j][v] = 구간 [i,j]에서 새롭게 생성한 두 수의 차가 v일때 최대 점수의 합

 

DP 초기화와 전이

일단 모든 dp 값을 -1 ( 불가능한 값을 나타내는 임의의 값) 으로 설정하고

혼자 남았을 때는 아무것도 진행할 수 없으므로 

dp[i][i][arr[i]] = 0 으로 초기화한다.

 

"인접한 두 수를 고르게 되면 두 수의 합 만큼의 점수를 얻게 되고

두 수가 사라짐과 동시에 해당 위치에 두 수의 차만큼에 해당하는 새로운 수가 추가된다고 합니다."

 

전이 가능 조건은 left , right로 나눴을 때

left = dp [ i ] [ k ] [ lv ] , right = dp [ k+1 ] [ j ] [ rv ] 로 나타낼 수 있으며 둘 다 불가능한 상태가 아닐때만 갱신해야한다.

newScore = lv + rv, newVal = abs(lv - rv) 일 때,
dp[i][j][newVal] = max(dp[i][j][newVal], dp[i][k][lv] + dp[k+1][j][rv] + newScore

-> 여기서 k는 i~j-1로 처리하는데 그 이유는 초기화할 때 len =1만 초기화해놓고 len = 2부터 돌리기 때문이다.

k = i 는 왼쪽 한칸짜리 분할, k = j-1는 오른쪽 한칸짜리 분할이기 때문에 반드시 포함해야 한다.

 

그리고 정답은 dp[0][N-1][ 0~10 ] 중 가장 큰 값으로 갱신해서 출력한다.

---

문제 - 유효한 문자열

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-valid-string/description

유효한 문자열 설명 | 코드트리

public class Main {
    static final int MOD = 10_007;

    // 두 문자가 짝이 될 수 있는지
    static int match(char a, char b){
        int cnt = 0;
        if((a == '(' || a == '?') && (b == ')' || b == '?'))
            cnt++;
        if((a == '{' || a == '?') && (b == '}' || b == '?'))
            cnt++;
        if((a == '[' || a == '?') && (b == ']' || b == '?'))
            cnt++;
        return cnt;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();
        int N = s.length;

        int[][] dp = new int[N][N];
        for(int i = 0; i<N; i++){
            dp[i][i] = 1;
        }

        for(int len = 2; len <= N; len++){
            for(int i = 0; i+len-1 < N; i++){
                int j = i+len-1;
                // k는 i와 짝이 되어야 함
                // A가 유효하면 [a] 이런식으로 감
                for(int k = i+1; k<=j; k+=2){
                    int cnt = match(s[i], s[k]);
                    if(cnt == 0)
                        continue;

                    /*
                    ()에서는 안쪽이 빈 문자열인데 
                    이때는 i+1 > k-1임 따라서 빈 문자열도 유효하다 했으니 1
                    오른쪽도 이때는 k+1 > j 이므로 1
                    */
                    int left = (i+1 < k-1) ? dp[i+1][k-1] : 1;
                    int right = (k+1 < j) ? dp[k+1][j] : 1;
                    dp[i][j] = (dp[i][j] + (cnt * left * right)) % MOD;
                }
            }
        }

        System.out.print(dp[0][N-1]);
    }
}

사고의 흐름 및 정리

-> 주석 참고

k가 len = 2인데 i+1부터 시작하는 이유는 

k의 경우 i와 짝이 되어야 해서 자기 자신과 짝을 한다는 것은 불가능하고 항상 [i][j]에서 i<j 형태를 만족해야 한다.