[ Baekjoon : python ] 백준 15990번 1, 2, 3 더하기 5 - 다이나믹프로그래밍

[  BAEKJOON ONLINE JUDGE  ] 15990 1, 2, 3 더하기 5 _ Python 파이썬

 

" 문제 "

 

www.acmicpc.net/problem/15990

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

---

" 아이디어 "

이 문제의 기본 뼈대는 [ 백준 9095번 1, 2, 3 더하기 ] 와 동일하다.

[ Baekjoon : python ] 백준 9095번 1, 2, 3 더하기 - 다이나믹프로그래밍

다만, 추가된 조건이 있다.

같은 수를 두 번 이상 연속해서 사용하면 안된다.

 

그렇기 때문에 기존 점화식을 일부 수정하여 풀어야 한다.

수를 필터링하기 위해 변수를 하나 더 추가한다.

 

D[i] = i를 1,2,3의 합으로 나타내는 방법의 수

-> D[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수 == j

 

간단한 예를 들어보면,

 

----- + 1 = i  (마지막에 1을 사용한 경우)	[---- + 2] + 1 --> D[i-1][2] [---- + 3]+ 1 --> D[i-1][3]	D[i][1] = D[i-1][2] + D[i-1][3]
----- + 2 = i  (마지막에 2를 사용한 경우)	[---- + 1] + 1 --> D[i-1][1] [---- + 3]+ 1 --> D[i-1][3]	D[i][2] = D[i-1][1] + D[i-1][3]
----- + 3 = i  (마지막에 3를 사용한 경우)	[---- + 1] + 1 --> D[i-1][1] [---- + 2]+ 1 --> D[i-1][2]	D[i][2] = D[i-1][1] + D[i-1][2]

여기서 2차원 배열을 이용하여 값을 따로 구했기 때문에 구하고자 하는 값은 D[n] 한줄의 값을 합한 것이다.

실제 코드에서 sum(d[n]) 을 하여 구한다.

 

한 가지 더 주의해야 할 점이 있다.

이전 9095번의 경우 모든 경우의 초기값을 D[0] = 1 (아무런 수도 사용하지 않은 경우) 로 초기화하여 풀어주었지만,

이 경우는 마지막에 사용한 수 j 가 존재하기 때문에 D[0] 으로 초기화해줄 수 없다.

D[0][1] = 1 로 초기화 하면

D[1][1] = D[0][2] + D[0][3] = 2 라는 오류가 발생!

 

그래서 문제의 최소단위를 찾아서 초기화해주어야 한다.

 

따라서 D[1][1] = 1, D[2][2] = 1, D[3][3] = 1 로 초기화한다.

(각각 자기 자신을 사용하여 만드는 방법은 1가지이므로)

 

---

" 코드 "

문제 조건에 맞게 답을 1000000009로 나누어 출력해야 한다.

그렇기 때문에 나머지 정리를 이용하여 각각의 d[i][1], d[i][2], d[i][3]을 나누고 최종 sum 값도 나누어준다.

수를 나눠주지 않으면 메모리초과가 발생한다.

 

import sys
input = sys.stdin.readline
 
max = 100000
mod = 1000000009
 
# 배열 초기화
d = [[0]*4 for _ in range(max+1)]
d[1] = [0,1,0,0]
d[2] = [0,0,1,0]
d[3] = [0,1,1,1]
 
# 배열 값 구하기
for i in range(4, max+1):
  d[i][1] = (d[i-1][2] + d[i-1][3])
  d[i][2] = (d[i-2][1] + d[i-2][3])
  d[i][3] = (d[i-3][1] + d[i-3][2])
 
  d[i][1] %= mod
  d[i][2] %= mod
  d[i][3] %= mod
 
T = int(input())
for _ in range(T):
  n = int(input())
  print(sum(d[n])% mod)
 

 

---

" 참고자료 "

 

hjp845.tistory.com/110

백준 15990 파이썬 python : 1, 2, 3 더하기 5 @@황소처럼 우직하게@@ 케케