Seeeni Tech Diary

[BOJ][Python] 20544번 공룡게임 본문

Algorithm/BOJ

[BOJ][Python] 20544번 공룡게임

seyeon0207 2023. 10. 10. 17:54

1. 문제

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

 

20544번: 공룡게임

크롬 브라우저 상에서 인터넷 연결이 안될때나, 주소창에 chrome://dino 를 입력하면 공룡 게임을 플레이 할 수 있다.

www.acmicpc.net


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
Comments