[백준] 9095, 15988, 15990: 1, 2, 3 더하기 1, 3, 5 (Python)

9095: 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이

정수 N을 1, 2, 3의 합으로 나타내는 방법은 N-1을 1, 2, 3의 합으로 나타내는 방법에 1을 더한 경우, N-2를 1, 2, 3의 합으로 나타내는 방법에 2를 더한 경우, N-3을 1, 2, 3의 합으로 나타내는 방법에 3을 더한 경우의 수의 합과 똑같다.
즉 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이다. 이 점화식을 이용해 코드를 작성하면 다음과 같다. 문제에서 n은 11보다 작은 양수라고 했으므로 dp 테이블의 크기는 11(인덱스 0~10)으로 설정했다.

# 9095: 400 - 다이나믹 프로그래밍 1 - 1,2,3 더하기
t = int(input())
n = [0]*t
for i in range(t):
    n[i] = int(input())

dp = [0]*11 # DP 테이블 초기화
dp[1] = 1
dp[2] = 2
dp[3] = 4 

for i in range(4, 11):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

for i in range(t):
    print(dp[n[i]])

 

 

---

15988: 1, 2, 3 더하기 3

https://www.acmicpc.net/problem/15988

15988번: 1, 2, 3 더하기 3

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이

위의 문제에서 n의 범위가 바뀌었고 결과를 1000000009로 나누어 출력하라는 지시사항이 추가되었다. 점화식을 그대로 이용하되 n의 범위를 max라는 변수로 설정해주었고 mod라는 변수에 결과를 나눌 수를 저장해 작성하였다. dp 테이블을 만들때 부터 mod로 나눠주지 않고 결과값을 출력할 때만 mod로 나누면 메모리 초과가 뜨므로 반드시 먼저 나눠주도록 한다. 

# 15988: 401 - 다이나믹 프로그래밍 1 연습 - 1,2,3 더하기 3
max = 1000000
mod = 1000000009
t = int(input())
n = [0]*t
for i in range(t):
    n[i] = int(input())

dp = [0]*(max+1) # DP 테이블 초기화
dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, max+1):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    dp[i] %= mod

for i in range(t):
    print(dp[n[i]])

 

---

15990: 1, 2, 3 더하기 5

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이

마찬가지로 n의 범위가 바뀌었고 출력 시 mod로 나누어주라는 지시사항이 추가되었다. 다만 여기서는 같은 수를 두 번 이상 연속해서 사용하면 안 된다는 제약 조건이 생겼다. 같은 수를 두 번 연속 사용하지 않기 위해서 N을 1, 2, 3의 합으로 표현하는 경우의 수를 맨 끝에 1이 오는 경우/2가 오는 경우/3이 오는 경우로 나누어 저장하였다. 이를 위해 2차원 리스트를 사용하였고, dp[n][1]을 구할 때는 dp[n-1][2]와 dp[n-1][3]의 합으로 계산하는 등 1이 연속해서 나오지 않게 처리하였다. 처음에는 dp[1], dp[2], dp[3]을 초기화할 때 0번 인덱스에 전체 경우의 합을 적었으나(예: dp[1] = [1, 1, 0, 0]) 맨 마지막에 출력할 때 sum함수를 이용하면서 합이 중복해서 더해지는 문제가 발생했기에 0번 인덱스의 값을 0으로 수정하였다.

# 15990: 400 - 다이나믹 프로그래밍 1 - 1,2,3 더하기 5
max = 100000
mod = 1000000009

dp = [[0]*4 for i in range(max+1)]

dp[1] = [0, 1, 0, 0] # 전체 경우의 수(추후 계산), 마지막 숫자가 1인 경우의 수, 마지막 숫자가 2인 경우의 수, 마지막 숫자가 3인 경우의 수
dp[2] = [0, 0, 1, 0]
dp[3] = [0, 1, 1, 1]

for i in range(4, max+1):
    dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % mod
    dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % mod
    dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % mod

t = int(input())
for i in range(t):
    n = int(input())
    print(sum(dp[n]) % mod)