https://www.acmicpc.net/problem/12101
12101번: 1, 2, 3 더하기 2
n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.
www.acmicpc.net
정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 사전순으로 정렬하여 k번째로 오는 식을 구하는 문제입니다.
먼저, N을 나타내는 방법의 수보다 k가 더 클수가 있기 때문에 dp배열에 N을 나타내는 방법의 수를 미리 저장하여 dp[N] < k이면 -1을 출력합니다.
다음은 문제 풀이 방법입니다.
예를들어, 4를 나타내는 방법은
1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1
이렇게 7가지가 있는데, 여기서 1~4번은 3에서 1은 더한 것, 5~6번은 2에서 2를 더한 것, 7번은 1에서 3을 더한 것임을 알 수 있습니다. 이제 dp[N - 1]와 k를 비교합니다.
k가 5라고 하면, dp[4] = 7 > k = 5이므로 k번째 식이 있습니다.
그러면 dp[3]과 k를 비교합니다.
(n = 4)(dp[3] = 4) < (k = 5) 즉, 3에서 1을 더한 식이 아니므로 dp[2]과 k - dp[3]을 비교합니다. (n은 그대로 유지)
(n = 4)(dp[2] = 2) > (k = 1) 즉, 2에서 2를 더한 식이므로 식에 "2+"를 추가하고 그 다음 순서를 확인하기 위해 dp[1]과 k를 비교합니다. (n은 idx값인 2로 바뀜)
(n = 2)(dp[1] = 1) = (k = 1) 즉, 1에서 1을 더한 식이므로 식에 "1+"를 추가하고 그 다음 순서를 확인합니다.
(n = 1) n이 1이므로 식에 '1'을 추가하여 완성된 식을 출력하고 리턴합니다.
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <iostream> #include <string> using namespace std; int dp[11], N, K; void init() { dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i = 4; i <= 10; i++) { dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; } } void func(int idx, int n, int k, string str) { if (n == 1) { str += '1'; cout << str << '\n'; return; } else if (n == 2 && k == 2) { str += '2'; cout << str << '\n'; return; } else if (n == 3 && k == 4) { str += '3'; cout << str << '\n'; return; } if (k > dp[idx]) { func(idx - 1, n, k - dp[idx], str); } else { str += (n - idx + '0'); str += '+'; func(idx - 1, idx, k, str); } } int main() { cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false); init(); cin >> N >> K; if (dp[N] < K) { cout << "-1\n"; return 0; } func(N - 1, N, K, ""); return 0; } | cs |
'algorithm > dp' 카테고리의 다른 글
| boj 15989 1, 2, 3 더하기 4 (0) | 2021.01.22 |
|---|---|
| boj 15988 1, 2, 3 더하기 3 (0) | 2021.01.22 |
| boj 9095 1, 2, 3 더하기 (0) | 2021.01.22 |
| boj 14226 이모티콘 (0) | 2021.01.22 |
| boj 17070 파이프 옮기기 1 (0) | 2021.01.22 |