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

안녕하세요!

2021년 마지막 날에도 이 문제를 풀고 있네요 ㅎㅎ

---

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

 

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

바로 이 문제입니다!

---

n=int(input())
data=[[0]*4 for _ in range(100001)]
data[1]=[0,1,0,0]
data[2]=[0,0,1,0]
data[3]=[0,1,1,1]

for i in range(4,100001):
  data[i][1]=data[i-1][2]+data[i-1][3]
  data[i][2]=data[i-2][1]+data[i-2][3]
  data[i][3]=data[i-3][1]+data[i-3][2]
  for j in range(1,4):
    data[i][j]%=1000000009

for i in range(n):
  num=int(input())
  print(sum(data[num])%1000000009)

(앞으로는 이렇게 코드 블록으로 코드를 보여드릴까 봐요! 더 깔끔하게 보기 좋은 듯!)

 

이 문제에서는, 기존에 풀었던 1,2,3, 더하기 문제와 유사하다.

그러나, 연속으로 같은 수가 오면 안 된다 라는 조건이 붙어있다.

그렇기에 우선 앞선 풀었던 다이내믹 프로그래밍 문제와는 다르게, 여기서는 이중 리스트를 이용해서 풀어야만 했다.

예를 들어서 data[7][3]이라면, 수들의 합을 더했을 때 7이 되는 경우이자, 마지막으로 더한 숫자가 3 임을 의미한다.

 

이런 식으로 100001번째 data까지 구하고, sum 연산을 통해 총 몇 개의 연산이 가능한지로 풀었다.

 

(아쉽게도 마지막에 sum을 구할 때 %100000009를 하지 않았는데, 앞에서 했다고 생각해서 쓰지 않았더니 data [i][1]+data [i][2]+data [i][3]를 더했을 때 100000009를 넘어서는 경우가 있지 않은가.... 이런 실수 때문에 알고리즘을 맞춰도 오답이라니!!!)

 

더 열심히 정진하겠다.

 

새해 복 많이 받으시고, 항상 화이팅 합시다잉!