[백준] 26093 고양이 목에 리본 달기 (DP)

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

제목

외로운 윤제는 고양이를 키우기로 했다.
 𝑁 마리의 고양이를 입양하기로 한 윤제는 고양이들에게 리본을 달아주기 위해 𝐾 종류의 리본을 충분히 준비했다. 즉, 각 리본의 개수는 무한하다. 각 고양이마다 리본의 종류에 따라 좋아하는 정도가 다르고, 이를 만족도로 나타낼 수 있다.
고양이들을 번호순으로 한 줄로 세우고 리본을 달아주려고 하는데, 각 고양이는 자신과 이웃한(왼쪽 혹은 오른쪽) 고양이와 같은 종류의 리본을 다는 것을 굉장히 싫어한다. 윤제는 고양이들이 싫어하는 상황을 피하면서 각 고양이의 리본에 대한 만족도의 총합을 극대화하고 싶다.
이 조건을 만족하는 만족도 합의 최댓값을 윤제에게 알려주자.
 

입력

첫 번째 줄에는 고양이의 수 𝑁과 리본 종류의 수 𝐾가 공백으로 구분되어 주어진다. (1≤𝑁≤100,2≤𝐾≤10000)
다음 𝑁개의 줄에는 각각 𝐾개의 정수 𝑎𝑖,1,⋯,𝑎𝑖,𝑘이 공백으로 구분되어 주어진다. (1≤𝑎𝑖,𝑗≤10000) 𝑎𝑖,𝑗는 𝑖번 고양이가 𝑗번 리본을 달았을 때의 만족도를 의미한다.

---

풀이

문제를 보자마자 DP의 냄새가 났다. 그러나 해결하는 데는 엄청난 시간이 걸렸다..
 
일단 문제에서 중요한 부분은 '각 고양이마다 리본의 종류에 따라 좋아하는 정도가 다르고' 이다.
 
1. 시간복잡도
각 고양이마다의 각 리본의 만족도를 고려하면 시간복잡도가 O(N^K^K) 즉, 100^10000^10000 이 되므로 시간초과가 뜰 것이다.
따라서 각 고양이마다 리본의 종류에 따른 만족도가 다르다는 점을 이용하여, 이전 dp (dp[i - 1])의 최댓값 2개만 고려할 수 있도록 로직을 짜야한다.
 
2. dp는 2차원 배열
dp[고양이 수][리본 종류 수] 로 만들었다.
dp[i][j]에는 0번째 고양이부터 (i - 1)번째 고양이의 만족도의 합의 최댓값 + i번째 고양이가 j번 리본을 했을 경우의 만족도의 합이 저장된다.
 
그렇게 처음 시도한 코드 ..

public class Main {
    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());
        int K = Integer.parseInt(st.nextToken());
        Integer[][] ribons = new Integer[N][K];
        Integer[][] dp = new Integer[N][K];

        // ribon 선호도 입력
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < K; j++) {
                ribons[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0] = ribons[0].clone();
        Integer[] before = dp[0].clone();
        Arrays.sort(before, Collections.reverseOrder());

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < K; j++) {
                if (dp[i - 1][j].equals(before[0])) {
                    dp[i][j] = ribons[i][j] + before[1];
                } else {
                    dp[i][j] = ribons[i][j] + before[0];
                }
            }
            before = dp[i].clone();
            Arrays.sort(before, Collections.reverseOrder());
        }
        int max = Arrays.stream(dp[N - 1]).max(Integer::compare).get();
        System.out.println(max);
    }
}

 
일단 위 코드는 시간초과가 떴다.
하지만, 일단 코드를 설명하겠다.
 
이 부분이 가장 중요하다.

if (dp[i - 1][j].equals(before[0])) {
    dp[i][j] = ribons[i][j] + before[1];
} else {
    dp[i][j] = ribons[i][j] + before[0];
}

 
if문의 의미는 i-1번 고양이가 j번 리본을 했을 때의 값과 이전 dp의 최댓값이 같은 경우이다. 즉, j번 리본을 했을 때가 이전 dp의 최댓값과 같다면, 이번에는 j번 리본을 선택할 수 없다. 리본이 연속되기 때문이다.
이러한 이유로 ribons[i][j] + before[1]; 처럼 이전 dp의 두 번째 최댓값을 더한다.
 
이번에는 통과한 코드이다.

public class Main {
    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());
        int K = Integer.parseInt(st.nextToken());
        Integer[][] ribons = new Integer[N][K];
        Integer[][] dp = new Integer[N][K];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < K; j++) {
                ribons[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0] = ribons[0].clone();

        for (int i = 1; i < N; i++) {
            int max1 = Integer.MIN_VALUE;
            int max2 = Integer.MIN_VALUE;
            for (int j = 0; j < K; j++) {
                if (dp[i - 1][j] > max1) {
                    max2 = max1;
                    max1 = dp[i - 1][j];
                } else if (dp[i - 1][j] > max2) {
                    max2 = dp[i - 1][j];
                }
            }

            for (int j = 0; j < K; j++) {
                if (dp[i - 1][j].equals(max1)) {
                    dp[i][j] = ribons[i][j] + max2;
                } else {
                    dp[i][j] = ribons[i][j] + max1;
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (int j = 0; j < K; j++) {
            if (dp[N - 1][j] > max) {
                max = dp[N - 1][j];
            }
        }
        System.out.println(max);
    }
}

 
달라진 부분은 전체적으로 최댓값과 두 번째 최댓값만 찾는다는 것이다.
 

 
통과~

 
 

 
요즘 방구석에서 컴퓨터 앞에 앉아서 코딩만 하니까 현타가.. 자주.. 온다..
일주일에 한 번은 나가서 놀아야겠다는 .. 생각을 해본다... (실천에 올릴지는 모름)