[Python] 백준 15990 1,2,3더하기5
https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 코드 작성 dp = [[0 for _ in range(3)] for _ in range(100001)] dp[1] = [1,0,0] dp[2] = [0,1,0] dp[3] = [1,1,1] mod = 1000000009 for i in range(4, 100001): dp[i][0] = (dp[i-1][1] + dp[i-1][2])%mod dp[i][1] = (dp[i-2][0] + dp[i-2][2])%mod dp[i][2] = (dp[i-3][..
[Python] 백준 9095 1,2,3더하기
https://www.acmicpc.net/problem/9095 코드 작성 k = int(input()) for _ in range(k): d = [0, 1, 2, 4] n = int(input()) for i in range(4, n+1): d.append(d[i-1]+d[i-2]+d[i-3]) print(d[n]) 코드 풀이 #1 이 문제는 다이나믹 프로그래밍으로 과거에 했던 연산을 누적하면서 수행해 나가는 문제이다. 우선 (1) 0을 1,2,3으로 표현하는 방법은 0가지 (2) 1을 1,2,3으로 표현하는 방법은 ’1‘ 1가지 (3) 2를 1,2,3으로 표현하는 방법은 ’1,1‘ ’2‘ 2가지 (4) 3을 1,2,3으로 표현하는 방법은 ’1,1,1‘ ’2,1‘, ’1,2‘, ’3‘ 4가지 (5) ..
