2022.03.03 [백준] (python 파이썬) 1, 2, 3 더하기

 

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

9095번: 1, 2, 3 더하기

---

풀이

다음 문제는 1,2,3을 더해서 n을 만들 수 있는 가지 수를 구하는 문제이다.

1,2,3이 중복해서 사용해도 되고, 갯수 제한이 없다. 그래서 dfs를 이용하여 코드를 작성했다.

for문안에 cnt배열을 만들어 각 케이스를 실행할 때, 초기화 되도록 만들었다.

dfs함수는 sum==target이면 cnt[target]가 카운팅된다. 그리고 만약 sum>target이면 범위를 넘었기 때문에 return시켜준다. 아래의 코드를 각 상황마다 배열을 초기화시켜주고 dfs함수를 돌린다.

import sys
 
sys.setrecursionlimit(10**6)
def dfs(sum,target,cnt):
    num=[1,2,3]
    if sum==target:
        cnt[target]+=1
        return
    elif sum>target:
        return
    for i in num:
        dfs(sum+i,target,cnt)
 
 
for i in range(int(input())):
    cnt = [0] * 11
    n=int(input())
    dfs(0,n,cnt)
    print(cnt[n])
 

 

아래의 코드는 위의 코드와 거의 동일하지만 문제에서 n이 11미만으로 범위가 좁기 때문에 전체 범위까지 dfs함수를 이용해 만들 수 있는 가지수를 저장하고 for문을 돌려 각 테스트케이스를 만들 수 있는 가지수를 바로 배열에서 출력했다.

import sys
 
sys.setrecursionlimit(10**6)
def dfs(sum,target,cnt):
    num=[1,2,3]
    if sum>target:
        return
    cnt[sum]+=1
    for i in num:
        dfs(sum+i,target,cnt)
 
cnt = [0] * 11
dfs(0,10,cnt)
for i in range(int(input())):
    n=int(input())
    print(cnt[n])