백준: 15989 1, 2, 3 더하기 4

1, 2, 3 더하기 시리즈

• 1, 2, 3 더하기
• 1, 2, 3 더하기 2
• 1, 2, 3 더하기 3
• 1, 2, 3 더하기 4
• 1, 2, 3 더하기 5
• 1, 2, 3 더하기 6
• 1, 2, 3 더하기 7
• 1, 2, 3 더하기 8
• 1, 2, 3 더하기 9

 

문제

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

 

문제 풀이

 기존의 1, 2, 3 더하기 문제와 다른 점이 있다면 순서가 다른 경우 하나의 경우로 생각한다는 것이다. 이를 구하기 위해서는 DFS로 조합을 구하는 방식으로 풀고자 한다면 N이 10000이라는 범위를 같기에 시간 초과가 발생한다. 따라서 DP로 문제를 풀어야 한다.

 

사용한 수 1, 2, 3의 순서로 구하면 답을 찾을 수 있다.

 문제를 풀기 위해 DP 배열을 구성한다면 위와 같은 규칙을 가짐을 알 수 있다. 예를 들어 N이 4라면 1, 2, 3으로 구할 수 있는 경우는 다음과 같다. 1의 경우 모두 1가지이다. 2의 경우 1의 경우의 수 + 앞에서 구한 경우의 수가 누적된다. 3의 경우도 2의 경우의 수를 구한 후에 앞의 경우의 수를 누적하여 구할 수 있다.

 

• 사용하는 수가 2이고 구하는 수가 2인 경우
  • 1로 구할 수 있는 경우의 수는 1이다.
  • 이로 구할 수 있는 경우의 수는 1이다. 따라서 2가 된다.
• 사용하는 수가 2이고 구하는 수가 4인 경우
  • 앞서 구한 2를 구할 수 있는 경우의 수는 2이고, 1로 구할 수 있는 경우는 1이므로 3이 된다.

 

따라서 2의 경우 `dp[i] += dp[i - 2]`와 같은 점화식을 세울 수 있고, 3의 경우 `dp[i] += dp[i - 3]`과 같은 점화식을 세울 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    t = int(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]

    for _ in range(t):
        n = int(stdin.readline())
        print(dp[n])