[백준 / BOJ] 12101 1, 2, 3 더하기 2 (cpp)

문제

출처 : https://www.acmicpc.net/problem/12101

12101번: 1, 2, 3 더하기 2

만들려는 숫자 n이 주어졌을때, n을 1,2,3을 이용해서 만들고 n을 만드는 경우의 수의 조합중 k번째를 찾아 출력하는 문제이다.

---

풀이

이런 유형의 DP를 풀어본적이 있어서 DP라고 착각했지만, n의 최댓값이 11로 작아서 완전탐색으로도 풀리는 문제다.

 

로직은 간단한데, 재귀를 이용해서 1,2,3으로 숫자 n을 만드는 모든 경우의 수를 저장해놓은다음 정렬 후 출력하면 된다.

주요 소스코드

void getComb(int num, string comb){
    if(num == n){
        results.push_back(comb.substr(1, comb.size()));
        return;
    }
    if(num > n) return;
    for(int i = 1; i <= 3; i++){
        int nextNum = num + i;
        if(nextNum > n) continue;
        getComb(nextNum, comb + "+" + to_string(i));
    }
}

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/12101%201%2C%202%2C%203%20더하기%202/main.cpp

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃