[백준/python] 15988번 1, 2, 3, 더하기 3

1. 문제

이 문제는 1, 2, 3 세 수를 사용하여 어떤 정수의 합을 나타내는 방법의 수를 구하는 문제이다.

특이한 점은 합을 나타낼 때 순서가 다르면 다른 방법이라는 것이다.

1+2와 2+1은 각각의 방법으로 취급된다.

 

2. 풀이

처음에는 dfs로 단순히 접근하여 모든 경우의 수를 확인하였다.

작은 숫자에서는 문제가 없었으나 테스트케이스 중 숫자가 커지면 어마무시하게 recursion이 일어나는 모양이다.

재귀 오류를 해결하니 시간 초과가 떠서 다른 방법으로 접근을 시도했다.

 

dfs가 시간초과가 날 때는 bfs 또는 dp 등등 새로운 방법을 시도할 때라는 거다.

dp를 사용하여 규칙성을 발견하였다.

 

처음에는 규칙을 잘못 발견했다.

단순히 1, 2, 4, 7로 증가되는 것만 확인하여 각각 차이가 1, 2, 3이니까 그 다음에 4를 더하나보다 했다.

그렇게 코드를 짜서 넣었더니 기본 테스트케이스도 실패...

 

4보다 큰 5를 넣었을 때 값이 13이 나오는 걸 보고 다시 규칙을 찾았다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

이런 규칙을 가지는 문제였고 이를 적용해 해결을 시도했으나 이번에는 메모리 초과가 떴다.

 

마지막에 1,000,000,009로 나누어 출력하라는 말에서 힌트를 얻어

dp 테이블 자체를 나머지 값을 저장하는 방식으로 바꾸었더니 해결이 되었다.

 

 

3. 코드

import sys
input = sys.stdin.readline

t = int(input())
case = [int(input()) for _ in range(t)]
dp = [0] * (max(case)+1)
dp[1], dp[2], dp[3] = 1, 2, 4
for i in range(4, len(dp)):
    dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])% 1000000009

for c in case:
    print(dp[c] )

 

4. 느낀점

아직은 문제를 보자마자 바로 적용해야 할 알고리즘이 무엇인지 알지 못한다.

감을 잡기 위해 더 많은 문제를 꾸준히 풀자!!