baekjoon - 15990

Problem. 1, 2, 3으로 표현하되 두 번 연속 사용 x

 

key point

1	2	3
1	2	1, 2 2, 1 3

기본 셋팅 값이 된다.

4	5	6
1, 3(o) 2, 2(x) 1, 2, 1(o) 2, 1, 1(x) 3, 1(o)	2, 3(o) 1, 2, 2(x) 2, 1, 2(o) 3, 2(o) 1, 3, 1(o) 2, 2, 1(o) 1, 2, 1, 1(x) 2, 1, 1, 1(x) 3, 1, 1(x)	pass

표현할 수 있는 숫자가 1, 2, 3 총 3개이기 때문에 n 번째 숫자의 값을 찾기 위해서는 n-1, n-2, n-3을 보면 된다.

더 자세하게는 n-1은 +1이 될 값들의 list이기 때문에 1로 끝나지 않는 숫자들의 개수를 알아야하고 같은 논리로 n-2는 2로 끝나지 않는 숫자들의 개수, n-3은 3으로 끝나지 않는 숫자들의 개수를 찾아야 한다.

 

그래서 메모리 build up을 dp = [0] * 100001, dp_1 = [0] * 100001, dp_2 = [0] * 100001, dp_3 = [0] * 100001으로 두고 1, 2, 3에 해당하는 값을 대입해주었다.

dp = [0] * 100001 dp_1 = [0] * 100001 dp_2 = [0] * 100001 dp_3 = [0] * 100001 dp[1] = 1 dp[2] = 1 dp[3] = 3 dp_1[1] = 1 dp_2[2] = 1 dp_1[3] = 1 dp_2[3] = 1 dp_3[3] = 1

dp[n]을 구하는 방법은 dp_1[n] = dp[n-1] - dp_1[n-1] //dp[n-1]의 값에서 1로 끝나는 숫자를 빼면 그게 n에서 1로 끝나는 숫자들의 갯수가 됨. (1~3 반복)

dp_1[i] = (dp[i - 1] - dp_1[i - 1]) % 1000000009  dp_2[i] = (dp[i - 2] - dp_2[i - 2]) % 1000000009  dp_3[i] = (dp[i - 3] - dp_3[i - 3]) % 1000000009

n = int(input()) dp = [0] * 100001 dp_1 = [0] * 100001 dp_2 = [0] * 100001 dp_3 = [0] * 100001 dp[1] = 1 dp[2] = 1 dp[3] = 3 dp_1[1] = 1 dp_2[2] = 1 dp_1[3] = 1 dp_2[3] = 1 dp_3[3] = 1 for i in range(4, 100001): #한 번에 계산을 해줘야 시간 초과를 피할 수 있음     dp_1[i] = (dp[i - 1] - dp_1[i - 1]) % 1000000009     dp_2[i] = (dp[i - 2] - dp_2[i - 2]) % 1000000009     dp_3[i] = (dp[i - 3] - dp_3[i - 3]) % 1000000009     dp[i] = dp_1[i] + dp_2[i] + dp_3[i]          for k in range(n):     num = int(input())     print(dp[num] % 1000000009)

+배열 선언에서 2차원 배열로 선언을 했으면 좋았겠지만 나의 경우는 dp_1이 1의 개수임을 나타내고 싶어서 그냥 따로 따로 배열을 선언해주었다.