159881 [백준_15988] 1, 2, 3 더하기 3 python 처음 문제를 풀었을 때 메모리 초과에 걸렸다. 왜일까 고민하다가 '방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.'에서 힌트를 얻었다. 디피를 채울 때 나머지만 넣어 줘도 상관이 없지 않을까 하는 생각을 했다. # dp 설계 dp = [ 0 for _ in range(1000001) ] # dp 초기설정 dp[1] = 1 dp[2] = 2 dp[3] = 4 # dp 채워넣기 for i in range(4, 1000001): dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % 1000000009 # t 입력 t = int(input()) # n 입력 for _ in range(t): n = int(input()) print(dp[n] % 1000000009) 2022. 7. 11. 이전 1 다음
