풀이 초기엔 재귀 함수를 사용해서 계속해서 값을 찾도록 했었지만 시간초과 이후 DP라고 해서 규칙을 찾고 난 다음 힌트를 얻게 됨. 우선 해당 수의 값은 1,2,3 번 이전의 수가 만들 수 있는 값의 합과 같다는 힌트를 얻음 그런데 여기서 또 해당 문제는 원하는 자릿수를 주기에 더 골치가 아팠다. 그래서 최대로 배열을 만든 다음 계속해서 값을 만들어준 다음 문제를 해결 정답 코드 def startSetting(): li[1][1] = 1 li[2][1] = 1 li[2][2] = 1 li[3][1] = 1 li[3][2] = 2 li[3][3] = 1 import sys input = sys.stdin.readline val = 1000000009 li = [[0]*1001 for _ in range(1..
