[백준] 9095번 : 1, 2, 3 더하기

문제

 

---

풀이

 

dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다.

3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호출한다.

---

소스코드

 

#include <iostream>

using namespace std;

int cnt;

void backtracking(int num) {
    if (num == 0) { //0이면 카운트 추가
        cnt++;
        return;
    }

    for (int i = 3; i >= 1; i--) { //3부터 1까지 뺄 수 있는지 확인
        if ((num - i) >= 0)
            backtracking(num - i);
    }
}

int main() {
    int t, n;

    cin >> t;
    for (int i = 0; i < t; i++) {
        cnt = 0;
        cin >> n;
        backtracking(n);
        cout << cnt << '\n';
    }
}

visited 관련 처리가 명시적으로 보이지 않아서 백트래킹이 아닌 것처럼 보일 순 있지만 맞다.