9095 - 1,2,3 더하기 - 완전탐색

문제

https://www.acmicpc.net/problem/9095

풀이전략

1. 1, 2, 3 으로만 표현해야 한다.
2. 1+3 과 3+1 은 다른 케이스이다.
3. 아무리 많은 계산을 한다고 하더라도 n의 최대값은 10이기 때문에 timecomplexity는 충분하다

코드

int n, c;
int cnt = 0;

void DFS(int num){
    /// num ==0 이라면 원하는 케이스를 찾은 것이므로 cnt를 더해준다
    if(num == 0){
        cnt++;
        return;
    }
    else{
    	// 1, 2, 3 으로 표현가능한지 보기
        // 지금보니 num-1이 어차피 불가하다면 그 밑에는 할필요가 없게끔 짜도 됨
        if(num - 1 >= 0){
            DFS(num-1);
        }
        if(num - 2 >= 0){
            DFS(num-2);
        }
        if(num - 3 >= 0){
            DFS(num-3);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    
    cin >> c;
    for(int k=0; k<c; k++){
        cin >> n;
        cnt = 0;
        DFS(n);
        cout<<cnt<<endl;
    }
    
    return 0;
}

소감