2281번 - 데스노트(dp)

문제:

 

풀이:

'계산할 때 제일 마지막 줄은 앞으로 이름을 적을 기회가 있으므로 계산하지 않는다.' 라는 말에 유의하자.

마지막까지 마지막줄은 포함해서 계산하지 않아도 된다는 말이다.

즉, 판단해야할 사항은,

1. 지금 몇번째 이름을 적고있는지
2. 지금 줄에 몇개의 글자가 적어져있는지
3. 지금까지 남게 되는 칸 수의 제곱의 합이 얼마인지(마지막줄 빼고!!)

나는 다음 과정과 같이 문제에 접근했다.

1. 맨 처음 이름을 기입한다.
   

   x

   x

   x

   x

   x

   x

   x

2. 칸이 남는다면, 두번째 이름을 바로 옆에 기입한다. 아직 마지막줄이므로, 제곱의 합 0이다.
   

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

3. 또한 두번째 이름을 밑에도 기입해본다. 이때는 제곱의 합이 13 x 13일 것이다.
   

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   이후 첫 줄을 고려하지 않아도 되므로 아래와 같이 글자배치를 생각한다.
   

   x

   x

   x

   x

   즉, 두번째 이름을 기입했을 때,
   7 + 1 + 4 번째 칸까지 글자가 적혀있을 때는 제곱의 합의 최솟값이 0이고,
   4번째 칸까지 글자가 적혀있을 때는 제곱의 합의 최솟값이 13이다. 
4. 세번째 이름을 작성해보자. 아래와 같이 4가지 경우가 나올 것이다.
   1. 12 + 1 + 2칸까지 글자가 적혀있을 때, 제곱의 합의 최솟값은 0
   

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   2. 2칸까지 글자가 적혀있을 때 제곱의 합의 최솟값은 8 x 8
   

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   x

   3. 4 + 1 + 2칸까지 글자가 적혀있을 때, 제곱의 합의 최솟값은 13 x 13
   

   x

   x

   x

   x

   x

   x

   4. 2칸까지 글자가 적혀있을 때, 제곱의 합의 최솟값은 13 x 13 + 16 x 16
   

   x

   x

   x

   x

   x

   x

   위에서 2번, 4번의 마지막줄 글자 수가 같은 것을 볼 수 있을 것이다.
   만약 다음에 이름을 적는다면 완벽히 같은 글자 수들이 나온다는 것을 상상할 수 있다.
   그렇다면 굳이 둘다 경우의 수를 생각해야 할까?
   전혀 아니다! 제곱의 합이 최솟값이 작은 쪽만 취해주면 된다!
   즉 다음 이름을 적을 때 고려할 경우는 아래와 같다.
   1. 15칸, 제곱의 합 0
   2. 7칸, 제곱의 합 13 x 13
   3. 2칸, 제곱의 합 8 x 8
5. 4번에서 설명한 방식대로 중복을 줄여나가며, 마지막 이름까지 써본다면, 
   '마지막까지 남게 되는 칸 수의 제곱의 합'의 최솟값을 구할 수 있을 것이다!
   아래서는 이 설명과 동일하게 코드를 작성하는 과정을 정리해놓았다.

 

먼저 입력을 위해 다음과 같은 전역변수를 설정해준다.

static int n, m;
static int[] names;
static int[][] dp;
static int min = Integer.MAX_VALUE;

• names: 이름을 순차적으로 저장
• dp[몇번째 이름을 적고있는지][지금 줄에 몇개의 글자가 적혀있는지] = 지금까지 남게 되는 칸 수의 제곱의 합
  즉, dp[판단1][판단2] = 판단3

이후 아래와 같이 입력을 받아준다.

Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();

names = new int[n];

for (int i = 0; i < n; i++) {
    names[i] = sc.nextInt();
}

dp = new int[n][m+1]; // 순번, 지금 층 합
for (int i = 0; i < n; i++) {
    Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[0][names[0]] = 0;

• dp배열을 Integer.MAX_VALUE로 초기화해줌
• dp[0][첫번째 이름] 은 0으로 초기화해줌

준비된 입력을 가지고 아래 메서드를 수행한다.

static void findMin() {
    for (int i = 1; i < n; i++) {
        int now = names[i];
        for (int j = 0; j <= m; j++) {
            if (dp[i-1][j] != Integer.MAX_VALUE) {
                if (j + now + 1 <= m) {
                    dp[i][j+now+1] = Math.min(dp[i-1][j], dp[i][j+now+1]);
                }
                dp[i][now] = Math.min(dp[i-1][j] + (m-j) * (m-j), dp[i][now]);
            }
        }
    }
}

1. 1 ~ n-1까지 반복한다. 이름을 순차적으로 기입하기 위해서이다. -- i
   1. 지금 순서의 이름은 now에 저장한다.
   2. 0 ~ m까지 반복한다. dp[i-1][j] 즉 이전 단계에서 해당 글자 수만큼 이름이 적힌적이 있는지 체크하기 위함. -- j
      1. 만약 dp[i-1][j] 가  Integer.MAX_VALUE이 아니라면, 
         이전 단계에서 해당 글자 수 만큼 이름이 적힌적이 있다는 의미
         1. 만약 j + now + 1이 m 보다 작다면, 즉 이름을 같은 줄에 이어적을 수 있다면,
            1. dp[i][j+now+1] = Math.min(dp[i-1][j], dp[i][j+now+1]);이다.
               이미 저장되어 있는 경우를 고려해, 위와 같은 과정을 거쳐야 한다.
               '같은 순번', '같은 글자 수'이지만, 다른 '지금까지 남게 되는 칸 수의 제곱의 합' 이라면,
               둘 중에 작은 값만 남기면 된다. 최솟값을 찾는 과정이기 때문이다.
         2. dp[i][now] = Math.min(dp[i-1][j] + (m-j) * (m-j), dp[i][now]);
            이 과정을 하는 이유는 다음 줄에 이름을 쓰기 위해서이다.
            다음 줄에 이름을 쓰고,  '지금까지 남게 되는 칸 수의 제곱의 합'을 업데이트 시키는 과정이다.
            이 또한  '지금까지 남게 되는 칸 수의 제곱의 합'은 작은 값만 남기면 된다.

위 반복문이 끝나고 나면, dp[n-1][0~20]사이에 '지금까지 남게 되는 칸 수의 제곱의 합'의 최솟값들이 저장되어 있다.

최솟값을 찾기 위해 아래 과정을 수행해준다.

findMin();

for (int i = 0; i < m; i++) {
    min = Math.min(min, dp[n - 1][i]);
}

System.out.println(min);

 

 

전체 코드:

import java.util.*;

public class 데스노트_2281번 {
    static int n, m;
    static int[] names;
    static int[][] dp;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        names = new int[n];

        for (int i = 0; i < n; i++) {
            names[i] = sc.nextInt();
        }

        dp = new int[n][m+1]; // 순번, 지금 층 합
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][names[0]] = 0;

        findMin();

        for (int i = 0; i < m; i++) {
            min = Math.min(min, dp[n - 1][i]);
        }

        System.out.println(min);
    }

    static void findMin() {
        for (int i = 1; i < n; i++) {
            int now = names[i];
            for (int j = 0; j <= m; j++) {
                if (dp[i-1][j] != Integer.MAX_VALUE) {
                    if (j + now + 1 <= m) {
                        dp[i][j+now+1] = Math.min(dp[i-1][j], dp[i][j+now+1]);
                    }
                    dp[i][now] = Math.min(dp[i-1][j] + (m-j) * (m-j), dp[i][now]);
                }
            }
        }
    }
}

 

 

시행착오:

지금까지 남게 되는 칸 수의 제곱의 합이 얼마인지(마지막줄 빼고!!) 이라는 설명이 있었을 것이다.

마지막줄 빼고를 강조한 이유는 내가 이를 무시했기 때문이다.

결국 마지막줄도 포함시켜야 하는줄 알고, 머리를 싸매고 끙끙거리고 있었다.

문제를 잘 읽자 ㅜ