[알고리즘][Python] 백준(BOJ) 9095 1, 2, 3 더하기_파이썬

DP

9095 1, 2, 3 더하기    www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

 

 

풀이 1

<내용>

• 제일 처음 이 문제를 풀 때는 DP라는 것을 잘 모를 때였다.
• 따라서, DP가 아닌 브루트 포스를 통해 접근한 풀이이다.

 

 

 

<코드>

def solve(s):
    global cnt
    for i in arr:
        res.append(i)
        if sum(res) == s:
            res.pop()
            cnt +=1
            break
        solve(s)
        res.pop()
    return cnt    

T = int(input())
for _ in range(T):
    s = int(input())
    arr = [1, 2, 3]
    res = []
    cnt = 0
    print(solve(s))

 

 

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 0은 0, 1은 1, 2는 2, 3은 4가지의 방법으로 나타낼 수 있다.
• 규칙을 찾으면 정수 n을 나타낼 방법은 (n-1에 1을 더하는 방법) + (n-2에 2를 더하는 방법) + (n-3에 3을 더하는 방법)이다.

 

 

 

<코드>

l = [0, 1, 2, 4]
for i in range(4, 11):
    l.append(l[i-1] + l[i-2] + l[i-3])

t = int(input())
for i in range(t):
    n = int(input())
    print(l[n])

 

 

 

 

 

 

 

 

 

풀이 3

<내용>

• 풀이 2의 방법과 같다.
• 미리 dp 배열의 크기를 정한다는 차이만 있다.

 

 

 

<코드>

dp = [0] * 12
dp[1], dp[2], dp[3] = 1, 2, 4

for i in range(4, 12):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]


t = int(input())
for _ in range(t):
    n = int(input())
    print(dp[n])