[실버 I] 15989번. 1, 2, 3 더하기 4

 문제 

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

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

 사용 언어 

Python3

 풀이 과정 

오랜만에 다시 DP 문제를 풀게 되었다.

그런데 이번에도 헷갈린 점화식 세우기...ㅎㅎ

처음엔 냅다 dp[i-1] + dp[i-2] + dp[i-3] 을 생각해봤는데 아무래도 중복되는 건 하나로 치는 경우 때문에 결과가 훨씬 크게 나왔다.

 

다시 곰곰이 생각해서 1을 더하는 경우는 항상 있기 때문에 초기화 숫자를 1로 변경하고 2를 더할 수 있는 경우 1개씩, 3을 더할 수 있는 경우 1개씩 더해주는 방식으로 변경했다.

 

제출했더니 맞았습니다!!

 

 제출 답안 

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        num = int(input())
        dp = [1] * (num + 1)
        for i in range(2, num + 1):
            dp[i] += dp[i-2]
        for i in range(3, num + 1):
            dp[i] += dp[i-3]
        print(dp[num])

 

 다른 사람 코드 

1부터 10까지 직접 써서 값을 구하고 점화식을 세워 구하셨다고 설명하는데 내가 dp[i-2] - dp[i-3] 값을 빼고 3의 배수이면(3을 더해서 만들어지는 수이면) 1을 더하는 방식이다.

for문을 한 번만 사용할 수 있다는 점에서는 좋은 것 같다.

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])

출처 : https://jshong1125.tistory.com/48