반응형
https://www.acmicpc.net/problem/2281
2281번: 데스노트
첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m
www.acmicpc.net
[ 문제풀이 ]
1. dp [ i ][ j ]에서 i는 현재 이름의 idx, j는 현재 줄에 쓰인 이름의 길이입니다.
2. 현재 idx의 이름을 현재 줄에 적을지 다음 줄에 적을지 선택하여 재귀 함수를 돌려줍니다.
3. dp[1][0]을 출력해줍니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include<iostream> #include<cstring> using namespace std; int n, m; int name[1001]; int dp[1001][1001]; //i번 이름, 해당 줄에 지금까지 쓰인 글자 수 int go(int idx, int len) //len = 가장 뒤의 공백 포함 { if (idx > n) return 0; int& ret = dp[idx][len]; if (ret != -1) return ret; //다음 줄에 쓰는 경우 ret = (m - len + 1) * (m - len + 1) + go(idx + 1, name[idx] + 1); //현재 줄에 쓰는 경우 if (len + name[idx] <= m) { ret = min(ret, go(idx + 1, len + name[idx] + 1)); } return ret; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &name[i]); } memset(dp, -1, sizeof(dp)); printf("%d", go(1, 0)); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1976번 - 여행 가자 (C++) (0) | 2022.11.11 |
|---|---|
| [ 백준 ] 12286번 - 돌 그룹 (C++) (0) | 2022.11.10 |
| [ 백준 ] 7569번 - 토마토 (C++) (0) | 2022.11.08 |
| [ 백준 ] 2195번 - 문자열 복사 (C++) (0) | 2022.11.07 |
| [ 백준 ] 2253번 - 점프 (C++) (0) | 2022.11.06 |