1, 2, 3 더하기 (완전탐색, 실버3)

문제 출처 : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

#1. 설계 및 풀이

 

# 1,2,3 더하기

'''
1<= n < 11

완전탐색

n이 될때까지 재귀함수 호출하면서 1, 2, 3을 더하기
n이 되면 cnt 증가
cnt 출력

'''


def dfs(res, n) :
    global cnt
    
    if res == n :
        cnt += 1
        return

    for i in range(1, 4) :
        if res+i <= n :
            dfs(res+i, n)

for _ in range(int(input())) :
    n = int(input())
    cnt = 0

    dfs(0, n)

    print(cnt)

 

- 처음부터 완벽하게 코드 짜려고 하지말자

 

- 테스트에서 생각하지 못했던 부분이 있을 수 도 있다.

문제와 예제들을 보면서 어떻게 풀지 방법 설정, 시간복잡도 계산해서 확신이 들면

손코딩 먼저 해보고 예제 돌아가는지 확인하고 코드로 옮기자.

 

- 해당 문제는 점화식 사용해서 DP로도 풀 수 있다.