[백준 9095번] 1,2,3 더하기 (C++ / Python)

아이디어는 간단하다.

n이 1~10까지 밖에 안되니

n이 10일때 3^10(59049)정도의 연산을 하기때문에 완전탐색으로 풀이가 가능하다.

그러므로 dfs를 통해 모든 경우의 수를 따져보면서

합이 target n보다 커지면 return해버리고 같아지면 count를 1증가시킨다.

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<string> v;
int N, target;
int cnt;
void dfs(int sum)
{
    if(sum ==target){
        cnt +=1;
        return;
    }
    else if (sum > target) return;

 //sum을 1,2,3씩 증가시켜본다.
    dfs(sum+1); 
    dfs(sum+2);
    dfs(sum+3);

}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 0 ;i < N; i++)
    {
        cin >> target;
        cnt =0;
        dfs(0);
        cout << cnt<<"\n";
    }
}

 

Python 풀이

import sys
input = sys.stdin.readline

def dfs(sum):
    global target,cnt
    if sum == target:
        cnt+=1
        return
    elif sum > target:
        return
    dfs(sum+1)
    dfs(sum+2)
    dfs(sum+3)

N = int(input().rstrip())
for _ in range(N):
    target=int(input())
    cnt = 0
    dfs(0)
    print(cnt)