백준 123더하기 9095

1. 백준 1,2,3더하기 9095

2. 컴퓨팅적 스킬

• DFS 재귀함수 이용
• vector에 테스트케이스 개수만큼의 값들을 넣어준 후, 반복문을 통해 각 경우에 대한 dfs를 호출하여 최종적으로 리턴되는값은 1,2,3으로 만들 수 있는 n에 대한 경우의 수입니다.
• dfs를 이해하기에 가장 좋은 예중 하나는 n과m문제입니다. 순열과 조합에 대표적인 문제입니다. 이 시리즈들을 모두 재귀로 한번 풀어보시길 바랍니다.
  N과 M시리즈 문제집

3. 컴퓨팅적 사고

• v == sum 일 경우 1,2,3으로 만들 수 있는 경우의 수 이기때문에 return 1을 해줍니다.
• v < sum 일 경우 return 0으로 현재 들어온 값을 재귀함수 종료시켜줍니다.
• dfs(v,n,sum+1) 1의 경우, dfs(v,n,sum+2) 2의 경우, dfs(v,n,sum+3) 3의 경우입니다.
• 1,2,3을 더하는 경우이므로 dfs(v,n,sum+1)+dfs(v,n,sum+2)+dfs(v,n,sum+3) 의 값을 반환시켜주면 현재까지 경우의 수를 반환시켜줍니다.
  언제 종료될것인가의 조건과 그 조건을 넘어섰을때 조건을 잘 생각해서 로직을 구현하여야 합니다.

---

4. 풀이

4.1. DFS

//
//  04_백준_1,2,3더하기_9095.cpp
//  algorithm-level-up
//
//  Created by kgh on 30/11/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;
int cnt = 0;
int dfs(int v, int n,int sum){
    
    //값에 부합할 경우
    if(v == sum){
        return 1;
    }
    //값의 범위를 넘어가게되면 그 이외의 값들이 들어가게되기때문에 반드시 필요한 조건
    if(v < sum){
        return 0;
    }
    
    return dfs(v,n,sum+1)+dfs(v,n,sum+2)+dfs(v,n,sum+3);
}
int main(void){
    
    int n=0;
    cin >> n;
    vector<int> v(n);
    
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    for(int i=0; i<v.size(); i++){
        cout << dfs(v[i], n, 0) << "\n";
    }
    return 0;
}