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

+ Recent posts

티스토리툴바