문제 : https://www.acmicpc.net/problem/15990
접근
- 다이나믹 테이블
dy를 만들고 양의 정수n에 대해dy[n]이 n을 1, 2, 3의 합으로 나타내는 방법의 수라고 하자. - 같은 수를 연속해서 더할 수 없으므로 다음과 같이 세 가지 경우로 나누어 생각해야한다.
- 마지막에 1을 더한 경우의 수는
dy[i-1]에서 마지막에 1을 더한 경우의 수를 뺀 값과 같다. - 마지막에 2를 더한 경우의 수는
dy[i-2]에서 마지막에 2를 더한 경우의 수를 뺀 값과 같다. - 마지막에 3을 더한 경우의 수는
dy[i-3]에서 마지막에 3을 더한 경우의 수를 뺀 값과 같다.
- 마지막에 1을 더한 경우의 수는
예를들어 3의 경우의 수는
1+2,2+1,3으로 총 3개이다. 4의 경우의 수를 구하려 할 때 마지막에 1을 더한 방법인2+1은2+1+1이 되므로 사용 할 수 없다. 즉 3에서 4로 갈 수 있는 경우의 수는 1을 제외하고 2와 3을 더한 경우의 수의 합과 같다 (1+1)
- 이를 배열로 나타내면
[1,1,1]과 같이 나타낼 수 있다.
dy[1]=[1, 0, 0]dy[2]=[0, 1, 0]dy[3]=[1, 1, 1]
- 그리고 4 이상의 수
i부터는 다음과 같이 구할 수 있다.
dy[i][0]=dy[i-1][1]+dy[i-1][2]dy[i][1]=dy[i-2][0]+dy[i-2][2]dy[i][2]=dy[i-3][0]+dy[i-3][1]
틀렸습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
input = sys.stdin.readline
if __name__=="__main__":
T = int(input())
lst = tuple(int(input()) for _ in range(T))
max_num = max(lst)
dy = [[0, 0, 0]] * (max_num+1)
dy[1] = [1,0,0]
dy[2] = [0,1,0]
dy[3] = [1,1,1]
devider = 1000000009
for i in range(4, max_num+1):
dy[i][0] = dy[i-1][1] + dy[i-1][2]
dy[i][1] = dy[i-2][0] + dy[i-2][2]
dy[i][2] = dy[i-3][0] + dy[i-3][1]
for num in lst:
print(sum(dy[num]) % devider)
위 코드에는 정답을 구할 수 없는 2가지 문제점이 있다.
올바른 2차원 리스트 선언하기
dy = [[0, 0, 0]] * (max_num+1)이 코드가 잘못되었다.만약
max_num = 4라고 했을 때, dy는 다음과 같다.[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]여기서
dy[0][1] = 1이라고 선언하면 어떻게 될까?
1
2
3
4
dy = [[0,0,0]] * 5
dy[0][1] = 1
print(dy)
# >>> [[0, 1, 0], [0, 1, 0], [0, 1, 0], [0, 1, 0], [0, 1, 0]]
왜?
dy = [0] * 5와 같이 배열을 생성했을 때, 파이썬은 사실int 0을 5개 생성하는 것이 아니라, 하나만을 생성하여 리스트의 모든 인덱스가 해당int 0하나를 가리키도록 한다.이때
dy[2] = 1과 같이 특정 인덱스에 값을 할당하면 그 때서야 새 정수가 생성되어dy[2]가 해당 정수를 가리키도록 하는 것이다.1차원 배열에서는 문제가 되지 않지만 2차원배열 부터는 다음과 같은 현상이 발생한다.
dy리스트의 모든 i인덱스는 똑같은 하나의 1차원 리스트를 가리키고 있기 때문에, 이 1차원 리스트의 값이 변경되면 모든 인덱스의 값이 변하는 것이다.
올바르게 선언하기
- 다음과 같이 for문을 이용하여 올바르게 선언하면 된다.
dy = [[0 for _ in range(3)] for _ in range(max_num+1)]이렇게 해야dy[i][j]에 해당하는 주소를 갖는 개별 int가 생성된다.
참고자료 : 링크 자세한 설명이 되어있다.
시간초과
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
input = sys.stdin.readline
if __name__=="__main__":
T = int(input())
lst = tuple(int(input()) for _ in range(T))
max_num = max(lst)
dy = [[0 for _ in range(3)] for _ in range(max_num+1)] # 이렇게 해야 list의 요소를 하나씩 바꿀 수 있다.
dy[1] = [1,0,0]
dy[2] = [0,1,0]
dy[3] = [1,1,1]
for i in range(4, max_num+1):
dy[i][0] = dy[i-1][1] + dy[i-1][2]
dy[i][1] = dy[i-2][0] + dy[i-2][2]
dy[i][2] = dy[i-3][0] + dy[i-3][1]
for num in lst:
print(sum(dy[num]) % 1000000009)
하지만 이 코드도 시간초과가 발생했다.
사실 이건 정말 간단한 문제였는데,
n이 커질수록dy[n]도 매우 급격하게 커진다는 것이다. 이러면 더하기 같은 간단한 연산이라도 연산에 걸리는 시간이 매우 커진다.문제에서도 1,000,000,009로 나눈 나머지를 출력하라고 하는 것이 힌트였다.
dy[i][j]값을 저장할 때 1,000,000,009의 나머지로 저장하면 값이 1,000,000,009 이상 커지지 않기 때문에 연산시간을 단축할 수 있다.
A=B + C일 때,A % n=B % n+C % n이므로 미리 나누어도 결과에 영향을 주지 않는다.
최종 개선 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
input = sys.stdin.readline
if __name__=="__main__":
T = int(input())
lst = tuple(int(input()) for _ in range(T))
max_num = max(lst)
dy = [[0 for _ in range(3)] for _ in range(max_num+1)] # 이렇게 해야 list의 요소를 하나씩 바꿀 수 있다.
dy[1] = [1,0,0]
dy[2] = [0,1,0]
dy[3] = [1,1,1]
devider = 1000000009
for i in range(4, max_num+1):
dy[i][0] = dy[i-1][1]%devider + dy[i-1][2]%devider
dy[i][1] = dy[i-2][0]%devider + dy[i-2][2]%devider
dy[i][2] = dy[i-3][0]%devider + dy[i-3][1]%devider
for num in lst:
print(sum(dy[num]) % devider)
많이 해메긴 했지만 결과적으로 파이썬에 대해 새로운 것을 배우는 유익한 시간이었다. 정수가 커지면 연산시간도 커진다는 당연한 사실을 왜 몰랐을까…