https://www.acmicpc.net/problem/15990
15990번: 1, 2, 3 더하기 5각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.www.acmicpc.net
처음에 보자마자 너무 막막했다.
살짝 힌트를 얻어서 풀었다.
이전 dp문제와는 달리, 배열을 [0,0,0,0]이 들어있는 2차원 배열로 만든다
[[0,0,0,0],[0,0,0,0]………….]
여기서 l[i][0]은 i를 만드는 경우의 수(정답),
l[i][1] 마지막이 1일때 i를 만드는 경우의수
l[i][2]마지막이 2일때 i를 만드는 경우의수
l[i][3]마지막이 3일때 i를 만드는 경우의수
를 뜻한다.
만일 l[i][1]을 구하고 싶다면, 마지막에 1을 더해야 하므로 l[i-1]에서 1을 더해야 한다.
하지만 문제의 조건상 1이 연속해서 나올 수 없으므로,
l[i-1]의 2, 3
즉 i보다 1 작은 수를 만들 때 끝이 1이 아닌 경우의 수의 합이
l[i]를 마지막에 1을 더해 만드는 경우의 수이다.
똑같은 방식으로 l[i][2]=l[i-2] 1,3 l[i][3]=l[i-3] 1,2가 된다.
이렇게 구한 l[i][1,2,3]의 합을 l[0]에 업데이트시켜주면 된다.
점화식을 세우면
l[i][0]= l[i][1]+ l[i][2]+ l[i][3]
l[i][1]=(l[i-1][2]+l[i-1][3])
l[i][2]=(l[i-2][1]+l[i-2][3])
l[i][3]=(l[i-3][1]+l[i-3][2])
이 된다.
수가 가면갈수록 기하급수적으로 커지므로
l[i][1],l[i][2],l[i][3] 을 구할때마다 %
1,000,000,009를 해주고
마지막에 l[i][0]을 구할 때 %
1,000,000,009를 해서 배열에 저장해주면 된다.
l=[[0,0,0,0]for _ in range(100001)]l[1]=[1,1,0,0]l[2]=[1,0,1,0]l[3]=[3,1,1,1]
l[4]=[3,2,0,1]for i in range(4,len(l)):
l[i][1]=(l[i-1][2]+l[i-1][3])%1000000009
l[i][2]=(l[i-2][1]+l[i-2][3])%1000000009
l[i][3]=(l[i-3][1]+l[i-3][2])%1000000009 l[i][0]=sum(l[i][1:])%1000000009
T=int(input())for _ in range(T): n=int(input()) print(l[n][0])개어려웠다. 이게 왜 실2?