[백준/Python] 15989번(DP)_1,2,3 더하기 4

📌문제 유형

DP (실버1)

 

📌문제

 

15989번: 1, 2, 3 더하기 4

 

📌나의 문제풀이

- 실패

• DP는 테이블 이용하여 이전 값 사용하기 (아니면 시간 넘겨서 출력초과 나타남)

t = int(input())
dp = [0] * 10001
dp[0] = 0
dp[1], dp[2], dp[3], dp[4] = 1, 2, 3, 4

for i in range(5,10001):
    if i % 2 == 0:
        dp[i] = 1 + (i//2) + 2**((i-1)//3)
    else:
        dp[i] = 1 + (i//2) + 2**(i//3)

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

 

📌 다른사람의 문제풀이

- 1+1 = 2 되는 경우는 (n-2)번씩 차이나서 1 더하기

- 1+1+1 = 3되는 경우는 (n-3)번씩 차이나서 1 더하기

[백준/Python(파이썬)] 15989 1, 2, 3 더하기 4

 

[ 백준 15989 해설 ] ( python ) 1, 2, 3 더하기 4

 

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
dp = [0 for _ in range(10001)]
dp[0], dp[1], dp[2], dp[3] = 1, 1, 2, 3
for i in range(4, 10001):
    dp[i] = dp[i-1] + (dp[i-2] - dp[i-3])
    if i % 3 == 0:
        dp[i] += 1
for i in a:
    print(dp[i])

import sys
input = sys.stdin.readline
dp = [1]*(10001)

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

T = int(input())

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

 

📌 리뷰 

- DP 경우의 수 따져보고 DP 테이블 안에서 계산하기