Seeeni Tech Diary
[BOJ][Python] 20544번 공룡게임 본문
1. 문제
https://www.acmicpc.net/problem/20544
2. 문제 풀이 알고리즘
1) DP 테이블 설계 (높이 2인 나무 필수 조건 생략)
1~n 지점에 높이가 1, 2인 나무를 놓거나 안 놓을 수가 있는데, 첫 지점에서는 나무가 없어야 한다. 나무는 연속 2개까지만 놓을 수 있고, 나무 2개의 높이의 합은 4 이상이 되어서는 안된다. 즉, 1-1, 1- 2, 2 -1은 되지만 2-2는 안 된다.
dp를 어떻게 사용할까 고민 하다가 현재 0(나무 없을 때), 1, 2 중 하나를 선택할 때 이전의 높이를 고려해야하고, 그 이외에는 고려할 필요가 없다는 점을 생각해낼 수 있었다.
0-0, 0-1, 0-2, 1-0, 1-1, 1-2, 2-0, 2-1. 2-2 이렇게 총 9개의 조합이 나올 수 있는데 이 중에서 2-2 조합만 없애면 된다.
(012)-0 | 0-1 | 1-1 | 2-1 | 0-2 | 1-2 | |
0 | 1 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 1 | 0 |
2 | 3 | 1 | 1 | 1 | 1 | 1 |
3 | 8 | 3 | 1 | 1 | 3 | 1 |
표(n = 4일 때)를 위와 같이 설계하고(코드에서는 일차원으로 설계했다), dp[0] = 1, 나머지는 0으로 초기화하였다.
현재가 0이 될 때는 이전의 어떤 경우도 가능하기 때문에 sum(dp)를, 0-1, 0-2일 때는 이전에 0이 었을 때의 경우의 수를 그대로 사용하였다.
1-1, 1-2는 이전에 1일 때의 조합이 1-1, 2-1이면 현재 세 개의 나무가 연속이 되는 것이기 때문에 이전의 0-1의 경우의 수를 가져왔다.
2-1의 경우도 마찬가지의 이유로 이전이 0-2 조합일 때의 경우의 수를 그대로 사용하였다.
이런 과정을 n -1 번 반복하고 난 후 모든 값을 더해주어 경우의 수를 구해주었다.
여기까지만 할 경우 문제에서 2인 나무가 하나라도 존재해야 한다는 조건을 놓치게 된다.
2) 높이 2인 나무가 없을 때의 경우의 수
(012)-0 | 0-1 | 1-1 | |
0 | 1 | 0 | 0 |
1 | 1 | 1 | 0 |
2 | 2 | 1 | 1 |
3 | 4 | 2 | 1 |
그래서 0, 1로만 조합이 존재할 때의 경우의 수를 찾은 다음 위의 경우의 수에서 제외하여 답을 구해주었다.
0, 1로만 이루어진 경우는 위의 표와 같이 구해주었다.
3) 전체 코드
n = int(input())
dp = [0] * 6
dp2 = [0] * 3
dp[0] = 1
dp2[0] = 1
for i in range(n - 1):
dp = [sum(dp), dp[0], dp[1], dp[4], dp[0], dp[1]]
dp2 = [sum(dp2), dp2[0], dp2[1]]
print((sum(dp) - sum(dp2)) % 1000000007)
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ][Java] 2252번 줄세우기 (0) | 2024.02.25 |
---|---|
[BOJ][Python] 20914번 QWERTY 자판 (1) | 2023.10.10 |
[BOJ][Python] 2638번 치즈 (0) | 2023.07.26 |
[BOJ][Python] 17143번 낚시왕 (0) | 2023.06.14 |
[BOJ][Python] 2146번 다리 만들기 (0) | 2023.05.14 |