[백준 2281] 데스노트(C++)

📕문제

---

사악한 라이토는 기발한 방법을 이용하여 L(애칭 섊)을 살해한 뒤 데스노트를 다시 손에 넣었다. 라이토는 이제 이 노트에 n명의 이름을 적어 넣으려고 한다. 이때 다음과 같은 조건을 만족시키면서 이름을 적어 넣으려 한다.

우선, 이름을 적어 넣을 때 이미 정해진 순서대로 n명의 이름을 적어 넣어야 한다. 이름을 적을 때도, 노트를 위에서 아래로, 같은 줄에서는 왼쪽 맨 끝에서 오른쪽으로 차례로 적는다고 하자. 또한 이름을 적을 때 각 사람의 이름 사이에 빈칸을 하나씩 두려고 한다. 한 줄을 적다가 그 줄의 끝에 한 사람의 이름이 다 들어가지 않고 잘리게 되면 반드시 새로운 줄에 이름을 써야 한다. 그렇지 않으면 이름이 중간에 잘려서 자칫하면 두 명의 사람이 죽게 된다. 이때, 각 줄의 끝에 사용하지 않고 남게 되는 칸의 수의 제곱의 합이 최소가 되도록 하려 한다. 이를 계산할 때 제일 마지막 줄은 앞으로 이름을 적을 기회가 있으므로 계산하지 않는다. 예를 들어 노트의 폭(너비)이 20인 다음의 경우를 보자.

각 사람의 이름의 길이가 차례로 7, 4, 2, 3, 2, 5, 1, 12, 7, 5, 6 인 경우이다. 위와 같이 적으면 차례로 1, 10, 0칸이 남아서 제곱의 합이 101이 된다. 반면에 아래의 경우에는 5, 6, 0칸이 남아서 제곱의 합이 61이 된다.

📕입력

---

첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m을 넘지 않는 자연수이다.

📕출력

---

첫째 줄에 남게 되는 칸 수의 제곱의 합의 최솟값을 출력한다.

 

🔎문제 해석

---

 이 문제는 내가 푼 DP문제중에서 젤 어려웠다. 어려워서 블로그 한번 보고 그 글을 참고로 풀었다.

굉장히 신박한 접근 방법이었고, 많이 배웠다. 나도 끝에서부터 시작을 해야겠다고 느꼈지만, 재귀로 짜기에 너무 복잡해서 처음을 시작으로 접근했지만, 확실히 처음으로 시작하니까 굉장히 코드가 복잡해지고, 시간 복잡도도 높아져서 아니라고 생각하고, 풀이를 봤다. [..ㅠㅠ..]

문제에서 중요 포인트는 내가 보기엔 2가지 정도가 있다.

• 너비를 넘긴다면 줄을 바꿔줘야함.[만약 억지로 꾸겨넣으면 두 사람으로 처리되서 문제 조건에 맞지 않음]
• 그리고 마지막 줄의 공백의 제곱의 합은 계산하지 않는다.[ 즉 DP[n-1]의 값은 0으로 고정되어 있다]
• 이  조건들을 이용해서 우리는 각 줄의 공백의 제곱의 합이 최소가 되도록 이름들을 배치해야한다.

 

DP [i] : i+1번째 이름을 새로운 줄에 쓸 때의 공백 제곱의 최솟값이라고 가정한다.

이게 무슨 뜻인지 쉽게 설명하자면 문제 입력의 예시를 들겠다. [n : 11 , m : 20]

폭	이름 개수	index	length
20	11	0	7
		1	4
		2	2
		3	3
		4	2
		5	5
		6	1
		7	12
		8	7
		9	5
		10	6

 

DP [10]은 마지막 이름을 새로운 즐에 쓸 때의 공백 제곱의 최솟값에 해당한다.

마지막 이름은 당연히 마지막 줄에 쓰일 것이다. 그러므로 DP [10]은 0이 될 것이다.

---

 

자 그러면 DP [9]를 결정해보자. DP [9]의 정의는 이제 다 알 것이라고 생각한다!

여기서 DP [9]는 두 가지 경우로 정해진다.

DP [10]을 DP [9]와 이어 붙일지, 아니면 따로 쓸지 두 경우 중에서 최소의 값을 정하면 된다.

name [10]을 이어 붙일 경우 : name[9]와 name[10]을 이어 붙이고, 공백 한 칸을 추가해준 것이 공백의 값이 될 것이다.

하지만  name [9]와 name [10]을 이어 붙인 경우 해당 줄은 마지막 줄 이기에 0이 된다.

새 줄에 쓸 경우 : 5칸을 제외한 15칸의 제곱의 합과 DP [10]을 더해준 값이 될 것이다. --> (225+ 0) = 225

DP [9]는 이어 붙일 경우와 새 줄에 쓸 경우 2가지 중 작은 값을 넣어줘야 하므로, 0이다.

---

 

DP [8]을 예시를 들어서 설명해 보겠다.

name [8]을 새 줄에 쓸 경우 :  name [8]의 길이에 해당하는 7을 뺀 13^2+DP [9] == -> 169

name [8]과 name [9]를 이어 붙이고, name [10]을 새로 쓸 경우 

(20-7-(5+1))^2 + DP [10] =  49 + 0 = 49

name [8]과 name [9]와 name [10]을 이어 붙이는 경우 : [단 항상 이어 붙일 수 있는지 없는지를 검사해야 함]

:마지막 줄 이므로 0이 된다.

따라서 DP [8]=0이 된다.

---

 

마지막으로 DP [7]을 예시를 들어 설명해 보겠다.

name [7]을 새 줄에 쓸 경우 :  (20-name [7])^2 + DP [8] =  64 + 0 = 64

name [8]을 이어 붙일 경우 : (20-name [7]-(name [8]+1))^2 + DP [9] = 0 + 0  0

name [8]과 name [9]를 이어 붙일 경우는 너비를 넘어서는 문자열의 길이가 되기 때문에 뒤에 경우는 계산을 안 해줘도 된다.

따라서 DP [7]은 최솟값인 0이 된다.

 

이렇게 쭉 쭉 구해보면

우리가 구하고자 하는 값은 DP [0]가 될 것이다.

DP [0]은 첫 번째 이름을 새 줄에 쓰는 경우이기 때문이다!!!!

 

🛑항상 이어 붙일 때 문자열의 길이가 폭을 넘지 안 넘는지를 체크하고 붙여줘야 한다!!

💻코드

---

/*
백준 골드4 데스노트
사용하지 않는 칸의 제곱의 합이 최소가 되어야함.
마지막 줄의 남는 칸은 계산하면 안됨.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>
using namespace std;
int n, m, now;
vector<int> name;
vector<int> DP; 
// DP[i]는 i번째 이름을 처음으로 쓸 경우의 공백의 최솟값을 넣어줌. 다음 칸을 붙일지 안붙일지만 결정해주면 됨.
int paper;
int dp(int step);
int main()
{
    cin >> n >> m;
    name.resize(n+1, 0), DP.resize(n+1,INT_MAX);
    for (int i = 0; i < n; i++)
    {
        cin >> name[i];
    }
    DP[n - 1] = 0; //마지막 줄은 공백을 계산하지 않아도 되기 때문에 0이다.
    cout<<dp(0)<<endl;
    
    return 0;
}
int dp(int step) { //step은 현재 내가 몇번째 이름까지 검사햇는지 체크하는 것.
    //이름이 너비를 넘지 않으면 일단 재귀를 넘겨보자.
    //현재상태에서 잔여칸은  잔여-name[i]가 될거같음.
    if (DP[step] < INT_MAX)
    {
        return DP[step];
    }
    
    int Paper = m - name[step]; //잔여를 계속 step마다 초기화함.
    for (int i = step + 1; i <= n && Paper >= 0; i++) { //현재 step 다음 거붙어 이어붙이는 거죵
        if (i == n) { //끝까지 돌았다는 뜻.
            DP[step] = 0;
            break;
        }
        DP[step] = min(DP[step], Paper * Paper + dp(i));
        Paper -= name[i] + 1; //종이를 이어붙인 경우 ,, 항상 이름+공백 한칸이 들어가기 때문에 뺴준다.
        //현재 step의 dp값은 이어붙일때와 이어붙이지 않을 때 중 최소값이 들어가게 될것이다.
    }
    return DP[step];
}

---

✔느낀 점

• 개어려웠다.
• 접근법이 엄청 참신해서 많이 배웠다.
• 보통 DP를 구할 때는 DP[n]을 구했지만 DP[0]으로 풀다니.. 이 사람 천재임