[JAVA] 백준 dp 부수기

 

 

 

9251 LCS - 골드5

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String a = br.readLine();
    String b = br.readLine();

    int[][] dp = new int[a.length()+1][b.length()+1];
    for (int i =0; i<a.length(); i++) {
        char c1 = a.charAt(i);
        int idx1 = i+1;

        for (int j =0; j<b.length(); j++) {
            char c2 = b.charAt(j);
            int idx2 = j+1;

            if (c1 == c2) {
                dp[idx1][idx2] = Math.max(dp[idx1][idx2], dp[idx1-1][idx2-1]+1);
            } else {
                dp[idx1][idx2] = Math.max(dp[idx1-1][idx2], dp[idx1][idx2-1]);

            }
        }
    }

    System.out.println(dp[a.length()][b.length()]);
}

유명한 LCS문제다. 점화식만 알고있다면 어렵지 않다.

 

 

17404 RGB거리 2 - 골드4

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int houseCnt = Integer.parseInt(br.readLine());

        int[][] cost = new int[houseCnt][3];
        int[][][] dp = new int[3][2][3]; //[첫번째 무슨색 채울건지][house 인덱스 % 2 값][rgb]

        //(0)입력받기
        for (int i = 0; i < houseCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //(1)초기화 작업
        for (int i =0; i<3; i++) {
            for (int j =0; j<2; j++) {
                Arrays.fill(dp[i][j], 1000000);
            }
        }

        dp[0][0][0] = cost[0][0];
        dp[1][0][1] = cost[0][1];
        dp[2][0][2] = cost[0][2];

        //(2)dp배열 갱신
        for (int i =1; i<houseCnt; i++) {
            int currentIdx = i % 2;
            int prevIdx = (i+1) % 2;

            for (int j=0; j<3; j++) {
                dp[j][currentIdx][0] = Math.min(dp[j][prevIdx][1] + cost[i][0], dp[j][prevIdx][2] + cost[i][0]);
                dp[j][currentIdx][1] = Math.min(dp[j][prevIdx][0] + cost[i][1], dp[j][prevIdx][2] + cost[i][1]);
                dp[j][currentIdx][2] = Math.min(dp[j][prevIdx][0] + cost[i][2], dp[j][prevIdx][1] + cost[i][2]);
            }
        }

        //(3)최솟값 구하기
        int currentIdx = (houseCnt-1) % 2;
        int result = Integer.MAX_VALUE;

        result = Math.min(result, dp[0][currentIdx][1]);
        result = Math.min(result, dp[0][currentIdx][2]);
        result = Math.min(result, dp[1][currentIdx][0]);
        result = Math.min(result, dp[1][currentIdx][2]);
        result = Math.min(result, dp[2][currentIdx][0]);
        result = Math.min(result, dp[2][currentIdx][1]);

        System.out.println(result);
    }
}

 

3차원 dp 배열로 해결했다. dp배열의 각 요소는 다음과 같음

• [3]: 빨강/초록/파랑 집으로 시작하는 경우
• [2]: 집의 인덱스를 %2 한 값 (모든 dp값을 저장할 필요가 없기 때문에 2개로 했다)
• [3]: (1~N)까지 채우고 현재 집을 칠한 색(RGB중 하나)

 

 

1106 호텔 - 골드4

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

 

느낌은 배낭문제와 굉장히 유사했다. 풀이는 크게 2가지 방법이 있다.

1. 특정 비용으로 늘릴 수 있는 최대 고객 수 구하기
2. 특정 고객 수를 위한 최소 비용 구하기

 

문제에 정확히 C명이 아니라 "적어도 C명"이라고 되어있기 때문에 C보다 높은 가장 최소 비용을 구해야한다. 그래서 1번과 2번방법 모두 column 범위를 크게 잡아줘야한다는 걸 알 수 있었다. 가장 처음에는 1번 방식으로 풀어봤다.

 

1106 - 1번 방식 풀이

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int requiredCnt = Integer.parseInt(st.nextToken()); // x <= 1000
    int cityCnt = Integer.parseInt(st.nextToken()); // x <= 20

    int[][] dp = new int[2][requiredCnt * 100 + 1]; //특정 비용으로 늘릴 수 있는 최대 고객 수 구하기

    for (int i =0; i<cityCnt; i++) {
        st = new StringTokenizer(br.readLine());

        int cost = Integer.parseInt(st.nextToken());
        int customerCnt = Integer.parseInt(st.nextToken());

        int current = i % 2;
        int prev = (i + 1) % 2;

        for (int j=0; j<dp[0].length; j++) {
            if (dp[current][j] < dp[prev][j])
                dp[current][j] = dp[prev][j];

            if (j < cost) {
                continue;
            }

            dp[current][j] = Math.max(dp[current][j], dp[current][j-cost] + customerCnt);
        }
    }

    //C명 이상이 되는 비용을 찾으면 break => 최소비용
    int tmp = (cityCnt-1) % 2;
    for (int i =0; i<dp[0].length; i++) {
        if (dp[tmp][i] >= requiredCnt) {
            System.out.println(i);
            break;
        }
    }
}

•  requiredCnt를 만들기 위해 사용해야할 최대 금액은 100 * requiredCnt이다. ("비용은 100 이하, 얻을 수 있는 고객수는 자연수"라고 문제에 명시되어 있다) 이 값을 column 크기로 지정하여 특정 비용으로 얻을 수 있는 최대 고객수를 dp배열에 저장했다.
• row는 2개만 사용하여 아껴썼다.
• requiredCnt 이상을 얻을 수 있는 비용을 for 루프로 찾아서 바로 반환하면 답을 구할 수 있다. 금액 범위는 넉넉하게 잡아줬기 때문에 무조건 답은 출력된다.

 

1106 - 2번 방식 풀이

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int requiredCnt = Integer.parseInt(st.nextToken()); // x <= 1000
    int cityCnt = Integer.parseInt(st.nextToken()); // x <= 20

    int[][] dp = new int[2][requiredCnt+101]; //특정 고객수를 만들기 위한 최소 비용
    Arrays.fill(dp[0], 100_001);
    Arrays.fill(dp[1], 100_001);

    dp[0][0] = 0;
    dp[1][0] = 0;

    for (int i =0; i<cityCnt; i++) {
        st = new StringTokenizer(br.readLine());

        int cost = Integer.parseInt(st.nextToken());
        int customerCnt = Integer.parseInt(st.nextToken());

        int current = i % 2;
        int prev = (i + 1) % 2;

        for (int j=0; j<dp[0].length; j++) {
            if (dp[current][j] > dp[prev][j])
                dp[current][j] = dp[prev][j];

            if (j < customerCnt) {
                continue;
            }

            dp[current][j] = Math.min(dp[current][j], dp[current][j-customerCnt] + cost);
        }
    }

    int tmp = (cityCnt-1) % 2;
    int min = Integer.MAX_VALUE;
    for (int i =requiredCnt; i<dp[0].length; i++) {
        if (dp[tmp][i] < min) {
            min = dp[tmp][i];
        }
    }

    System.out.println(min);
}

• dp로 갱신해야할 고객 수 범위는 requiredCnt + 100이다. "적어도 C명 이상"이라고 명시되어 있기 때문에, "정확히 C명"인 비용보다 "C명보다 큰 고객수"일 때 비용이 더 낮을 수도 있다. 비용의 범위는 100이하이기 때문에 크기는 최대 requiredCnt+100밖에 되지 않는다.
• 위 방식과 마찬가지로 row는 2개만 사용하여 아껴썼다.
• "정확히 C명"일 때의 비용부터 "C명보다 큰 고객수"일 때의 비용을 모두 비교하여 최솟값을 min에 넣어주고 출력해주면 답이 나온다.

 

column 범위가 1번이 훨씬 크기 때문에 계산 횟수도 더 많다. 그래서 2번이 성능이 더 좋게 나오는 걸 확인할 수 있었다.

 

 

1958 LCS3 - 골드4

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String a = br.readLine();
    String b = br.readLine();
    String c = br.readLine();

    int[][][] dp = new int[a.length()+1][b.length()+1][c.length()+1];
    for (int i =0; i<a.length(); i++) {
        char c1 = a.charAt(i);
        int idx1 = i+1;

        for (int j =0; j<b.length(); j++) {
            char c2 = b.charAt(j);
            int idx2 = j+1;

            for (int r=0; r<c.length(); r++) {
                char c3 = c.charAt(r);
                int idx3 = r+1;

                //모두 같으면
                if (c1 == c2 && c2 == c3) {
                    dp[idx1][idx2][idx3] = dp[idx1-1][idx2-1][idx3-1] + 1;
                } else {
                    //idx1은 고정이라고 생각하기
                    dp[idx1][idx2][idx3] = Math.max(dp[idx1][idx2-1][idx3], dp[idx1][idx2][idx3-1]);
                    dp[idx1][idx2][idx3] = Math.max(dp[idx1][idx2][idx3], dp[idx1-1][idx2][idx3]);
                }
            }
        }
    }

    System.out.println(dp[a.length()][b.length()][c.length()]);
}

3차원 dp를 써야할 것 같다는 느낌이 왔다. 3가지 글자를 동시에 비교하고 갱신해야한다는 점만 고려하면 2차원 LCS와 유사하게 풀이할 수 있었다.

 

 

2133 타일 채우기 - 골드4

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    if (n % 2 == 1) {
        System.out.println(0);
        return;
    }

    int[] dp = new int[n+1];
    dp[0] = 1;

    //1. ||_ 3x2
    //2. _|| 3x2
    //3. =_ 3x2
    //4. __ |=| 3x4 3x6 3x8 ...
    //5. |=| __ 3x4 3x6 3x8 ...

    for (int i =2; i<dp.length; i+=2) {
        dp[i] = dp[i-2] * 3;

        if (i >3) {
            int tmp = 2;
            while (i - tmp*2 >= 0) {
                dp[i] += 2*dp[i - tmp*2];
                tmp++;
            }
        }
    }

    System.out.println(dp[dp.length-1]);
}

처음엔 막막할 수 있지만, 나올 수 있는 경우가 한정적이라는 걸 알고나면 굉장히 쉬워지는 문제다. 나올 수 있는 경우의 수는 아래의 5가지 경우가 끝이다.

 

나눠보면 5가지가 나오고, 마지막 2개는 +2개씩 무한하게 늘어날 수 있다. 

123번째로 dp배열 경우의 수를 채워주고, 45번째를 while문으로 더해주면 답이 금방 나온다.

 

+) 홀수인 경우는 구할 수 없기 때문에 0을 반환해주면 된다

 

 

2631 줄 세우기 - 골드4

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

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cnt = Integer.parseInt(br.readLine());

    int[] arr=  new int[cnt];
    int[] dp = new int[cnt];

    for (int i = 0; i < cnt; i++) {
        arr[i] = Integer.parseInt(br.readLine());
    }

    int max = 0;
    for (int i =0; i<cnt;i++) {
        dp[i] = 0;
        for (int j =0; j<i; j++) {
            if (arr[j] < arr[i]) {
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    max = Math.max(dp[i], max);
                }
            }
        }
    }

    System.out.println(cnt - max);
}

(문제가 굉장히 귀여워서 마음에 든다)

LIS라는 생각도 못했는데, LIS였다. 최장 증가 수열 개수를 찾아내서 고정시키고 나머지 애기들만 옮겨주면 최소 횟수로 옮길 수 있다.

 

 

1516 게임 개발 - 골드3

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

class Node implements Comparable<Node> {
    int id;
    int cost;

    public Node(int id, int cost) {
        this.id = id;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.cost, o.cost);
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int typeCnt = Integer.parseInt(br.readLine());
        List<Integer>[] relation = new ArrayList[typeCnt];
        List<Integer>[] dependsOn = new ArrayList[typeCnt];

        for (int i =0; i<typeCnt; i++) {
            relation[i] = new ArrayList<>();
            dependsOn[i] = new ArrayList<>();
        }

        boolean[] clear = new boolean[typeCnt];
        int[] times = new int[typeCnt];

        for (int i = 0; i < typeCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            //건축 시간 추가
            int time = Integer.parseInt(st.nextToken());
            times[i] = time;

            while (true) {
                int value = Integer.parseInt(st.nextToken());
                if (value == -1) {
                    break;
                }

                dependsOn[i].add(value-1);
                relation[value-1].add(i);
            }
        }

        int[] minTime = new int[typeCnt];
        Arrays.fill(minTime, Integer.MAX_VALUE);

        Queue<Node> queue = new PriorityQueue<>();
        for (int i = 0; i < typeCnt; i++) {
            if (dependsOn[i].isEmpty()) {
                queue.add(new Node(i, times[i]));
                minTime[i] = times[i];
            }
        }

        //dijkstra
        while (!queue.isEmpty()) {
            Node poll = queue.poll();

            if (poll.cost > minTime[poll.id]) {
                continue;
            }

            clear[poll.id] = true;

            for (int near: relation[poll.id]) {
                //다 안지어졌으면 ㄴㄴ
                boolean canStart = true;
                int maxTime = times[poll.id];
                for (int mom: dependsOn[near]) {
                    if (!clear[mom]) {
                        canStart = false;
                        break;
                    }
                    maxTime = Math.max(maxTime, minTime[mom]);
                }

                if (!canStart) {
                    continue;
                }

                if (minTime[near] > maxTime + times[near]) {
                    minTime[near] = maxTime + times[near];
                    queue.add(new Node(near, times[near]));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < typeCnt; i++) {
            sb.append(minTime[i]).append("\n");
        }

        System.out.print(sb);
    }
}

다익스트라로 풀릴 것 같아 해봤더니 풀렸다.

나는 queue에 넣을 때, 의존하는 건물이 모두 세워진 건물만 queue에 넣어주도록 했다.

+) 이 때 (의존하는 건물들 중 세워진 시간이 가장 큰 건물의 지은 시간 + 현재 건물이 지어지는 시간)이 현재 건물이 지어지는 시간이라는 걸 유의해야한다. 

 

이 문제는 위상정렬로도 풀 수 있다고 한다. 위상정렬이 기억나지 않아서.. 위상정렬로 푼 블로그를 첨부하겠다.

https://steady-coding.tistory.com/86

 

 

2342 Dance Dance Revolution - 골드3

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[][][] dp = new int[100_001][5][5]; //넉넉하게 최댓 값으로 초기화
        StringTokenizer st = new StringTokenizer(br.readLine());

        int idx = 0;
        int last = 0; //마지막 발자취 저장

        //두 발 모두 0에서 시작
        for (int i = 0; i < 5; i++) {
            Arrays.fill(dp[0][i], 400001);
        }
        dp[0][0][0] = 0;

        while (true) {
            int value = Integer.parseInt(st.nextToken());
            if (value == 0) {
                break; //입력 끝
            }

            int current = ++idx;

            //초기화
            for (int i = 0; i < 5; i++) {
                Arrays.fill(dp[current][i], 400001);
            }

            //dp하기 - value를 밟기위한 모든 경우 계산
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    int strength = getStrength(j, value);
                    dp[current][i][value] = Math.min(dp[current][i][value], dp[current - 1][i][j] + strength);
                    dp[current][value][i] = Math.min(dp[current][value][i], dp[current - 1][j][i] + strength);
                }
            }

            last = value;
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 5; i++) {
            min = Math.min(min, dp[idx][i][last]);
            min = Math.min(min, dp[idx][last][i]);
        }

        System.out.println(min);
    }

    private static int getStrength(int a, int b) {
        if (a == b) {
            return 1;
        }

        if (a == 0) {
            return 2;
        }

        if (Math.abs(a - b) == 2) {
            return 4;
        }

        return 3;
    }
}

dp는 3차원 배열을 사용해줬다. 각각은 다음을 의미한다 

[ㅇ][][]:  밟아야하는 발판의 인덱스

[][ㅇ][]: 왼발 위치

[][][ㅇ]: 오른발 위치

 

특정 step을 밟을 때 초기화해주는 로직은 다음과 같다.

ex) 4를 밟아야하는 상황

1. 오른발로 4를 밟기: dp[current][i][4] = Math.min(dp[current][i][4], dp[current-1][i][j] + 발옮기기비용)
2. 왼발로 4를 밟기:  dp[current][4][i] = Math.min(dp[current][4][i], dp[current-1][j][i] + 발옮기기비용)

여기서 i와 j는 0~4까지 이중루프로 돈다. 그냥 모든 발 위치인 경우를 다 고려해서 dp배열을 갱신한다고 보면된다.

발을 옮기는 비용은 메서드로 따로 빼줬다. 문제에 명시되어있는 그대로 구현해주면 된다.