15990번 파이썬

처음엔 아래 코드처럼 p[n]을 구하기 위해서 p[n-1]에 앞뒤로 1을 붙여주거나 p[n-2]에 2를 붙여주거나 p[n-3]에 3을 붙여주는 방법으로 해봤는데 시간 초과 에러가 떴다.

import sys
input = sys.stdin.readline
t = int(input())
p = [(0) for _ in range(100002)]
div = 1000000009
p[1] = [['1']]
p[2] = [['2']]
p[3] = [['1', '2'], ['2', '1'], ['3']]
for _ in range(t):
  n = int(input())
  if n > 3:
    for num in range(4, n+1):
      if p[num] != 0:
        continue
      ary = []
      for i in range(1, 4):
        plus = list(str(i))
        for t in p[num-i]:
          back = t+plus
          front = plus+t
          check = False
          if front not in ary:
            for idx in range(len(front)-1):
              if front[idx] == front[idx+1]:
                check = True
            if not check:
              ary.append(front)
          if back not in ary:
            for idx in range(len(back)-1):
              if back[idx] == back[idx+1]:
                check = True
            if not check:
              ary.append(back)
      p[num] = ary
  print(len(p[n]) % div)

그래서 다른 사람 방법을 참고해봤더니 아래처럼

p[idx][1]에는 끝자리가 1로 끝나는 수의 개수를 저장하고 p[idx][2]와p[idx][3]도 마찬가지로 그 숫자로 끝나는 수의 개수를 저장했다.

끝에 1을 붙일 수 있는 경우의 수는 n이 idx-1번째 값중 2,3으로 끝날때이고

2를 붙일 수 있는 경우의 수는 n이 idx-2번째 값중 1,3으로 끝날때이고

3을 붙일 수 있는 경우의 수는 n이 idx-3번째 값중 1,2로 끝날때이다.

import sys
input = sys.stdin.readline
p = [[0 for _ in range(4)] for _ in range(100001)]
div = 1000000009

p[1] = [0,1,0,0]
p[2] = [0,0,1,0]
p[3] = [0,1,1,1]

for idx in range(4,100001):
  p[idx][1]=(p[idx-1][2]+p[idx-1][3])%div
  p[idx][2]=(p[idx-2][1]+p[idx-2][3])%div
  p[idx][3]=(p[idx-3][2]+p[idx-3][1])%div
t = int(input())
for _ in range(t):
  n = int(input())
  print(sum(p[n]) % div)