[백준] 1309 동물원 - 실버 1

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• DP
• 구현

---

1. 문제설명

 

가로로 2칸 세로로 N칸인 동물원에 사자를 배치하는 경우의 수를 구하는 문제 입니다.

 

경우의 수에는 사자를 1마리, 2마리 ,,, N 마리 등 다양한 경우의 수가 존재하는데 사자를 아예 배치하지 않는 것도 경우의 수 중 하나라고 합니다.

---

[제한사항]

• 시간 제한 2초
• 메모리 제한 128MB
• 1≤ N ≤100,000
• 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다.

---

2. 접근방식

이 문제는 점화식만 세우면 쉽게 해결할 수 있습니다.

 

우선 동물원 울타리가 1칸만 주어지는 경우를 살펴보죠

 

1칸이 주어진다면 넣을 수 잇는 경우의 수는 다음과 같습니다.

 

 

사자를 아예 넣지 않는 경우 1마리만 넣는데 좌, 우 하나씩 넣는 경우

 

총 3가지가 존재하죠

 

사자는 주위에 사자가 없어야 하므로 상,하,좌,우 에는 사자가 존재하면 안됩니다.

 

따라서 이런 경우의 수 3가지가 나오게 됩니다.

 

이제 동물원의 크기가 2로 커진 경우를 보겠습니다.

 

 

동물원의 크기가 2 x 2로 커진 경우 사자를 배치하는 경우의 수는 다음과 같습니다.

 

사자가 겹치지 않도록 1마리씩 4칸에 넣는 경우, 2마리를 대각으로 배치하는 경우, 아예 넣지 않는 경우로 총 7가지가 존재합니다.

 

기존의 경우의 수와 동일하게 아예 넣지 않는 경우, 1마리만 넣는 경우를 제외하고

 

2마리를 넣을 때 넣을 수 있는 경우의 수를 계산해 주어야 합니다.

 

기존에 1마리만 넣는 경우에도 경우의 수가 늘어났고, 2마리가 들어갈 때 경우의 수가 더 늘어났죠

 

이제 동물원의 크기가 2 x 3 으로 더 커진 경우를 보겠습니다.

 

 

동물원의 크기가 더 커진 경우 사자를 배치할 수 있는 경우의 수는 다음과 같습니다.

 

아예 넣지 않는 경우의 수 = 1

 

1마리만 넣는 경우의 수 = 6

 

2마리 넣는 경우의 수 = 7

 

3마리 넣는 경우의 수 = 2

 

이렇게 볼 때 경우의 수 들은 1, 3, 7, 17 로 늘어났죠

 

하나의 규칙이 보입니다. 바로 현재 동물원의 사자를 배치하는 경우의 수는 이전에 배치한 사자의 경우의 수 x2 에 2회 전에 배치한 경우의 수를 더한값과 동일합니다.

 

즉 7의 경우 3 x 2 + 1 과 동일하고

 

17의 경우 7 x 2 + 3 과 동일합니다.

 

그렇다면 N = 4 인 경우 사자를 배치할 수 있는 경우의 수는 17 x 2 + 7 과 동일하겠죠 이를 계산하면 41이고 예제와 맞아 떨어지게 됩니다.

 

좀 더 쉽게 알아보죠 

 

 

위 그림을 통해 알 수 있는 것은 사자를 아예 배치하지 않는 경우의 수와 왼쪽 1번 우리에 배치하는 경우 오른쪽 2번 우리에 배치하는 경우 입니다.

 

N = 1 이라면 사자를 아예 배치하지 않는 경우의 수 1개, 왼쪽우리에 배치하는 경우 1개, 오른쪽 우리에 배치하는 경우 1개로 총 3개가 존재하죠

 

N = 2 라면 사자를 아예 배치하지 않는 경우의 수는 앞선 우리에서 아예 배치를 하지 않은 경우, 왼쪽에 배치한 경우, 오른쪽에 배치한 경우 상관없이 모두 배치할 수 있죠 

 

따라서 3가지 경우가 존재합니다.

 

N = 2 일때 왼쪽 우리에 배치하는 경우의 수는 앞선 우리에서 사자를 배치하지 않은 경우와 오른쪽 2번 우리에 배치한 경우 2가지가 존재합니다.

 

마찬가지로 오른쪽 우리에 배치하는 경우도 사자를 배치하지 않는 경우와 1번 우리에 배치한 경우인 2가지가 존재하죠

 

따라서 위 그림처럼 7가지의 경우가 존재합니다.

 

동일하게 3의 경우 그럼 사자를 아예 배치하지 않는 경우는 앞선 7가지의 경우 모두에 포함되니 7이 되고

1번의 경우 사자를 배치하지 않는 3가지 경우의 수에 2번 우리에 배치하는 2가지 경우의 수를 더해 5가 되죠

2번도 동일하게 5가 되겠죠

 

 

따라서 이렇게 17이 됩니다.

 

동일하게 반복하면 위 그림은 이렇게 채워지겠죠

 

 

이렇게 2가지 방법으로 점화식을 찾았습니다. 둘 중 하나를 코드로 구현해 보았습니다.

---

3. 코드

import sys
input = sys.stdin.readline

N = int(input())
DP = [1] * (N + 1)

for i in range(1, N + 1):
    DP[i] = (DP[i - 1] * 2 + DP[i - 2]) % 9901

print(DP[N])

---

[코드설명]

 

코드가 단순해 크게 어려운 것이 없습니다.

 

DP 테이블을 초기화 할때 테이블을 1로 초기화 한 이유는 DP[0] 으로 우리가 없어 사자를 아예 배치할 수 없는 경우도 경우의 수가 존재하는 것으로 봐서 1이기 때문에 DP 테이블을 1로 초기화 하였습니다.

 

여기에 앞서 찾은 점화식을 토대로 현재의 DP 값은 이전 DP값의 2배에 2회전 DP 값을 더해준 값과 동일하니 이렇게 입력해 주었습니다.

 

출력에서 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하라고 했는데

 

N이 최대 100,000 이 주어지므로 주어진 DP를 그대로 돌리는 경우 배열의 메모리를 초과하는 값이 입력되기 때문에

 

배열에 저장 자체를 9901로 나눈 값으로 저장해 주었습니다.

---

4. 결과

---

[회고]

 

이번문제는 해결에 시간이 오래 걸리지 않았습니다.

 

문제를 정의하고 점화식을 세우고 문제를 풀기까지 약 15분 정도 걸렸던 거 같습니다.

 

점화식을 세우는 것도 excel을 통해 중복을 제거하여 그림을 통해 가시적으로 세우니 한번에 점화식을 찾을 수 있었고

 

찾은 점화식을 토대로 문제를 바로 해결할 수 있었습니다.

 

그러나 찾아온 점화식은 사실상 때려맞춘 점화식에 불과하기 때문에 논리적으로 올바른 점화식을 찾아 보았습니다.

 

그러다 찾은 점화식이 앞선 표로 찾은

 

 

 

이 점화식 이었습니다.

 

사자를 아예 배치하지 않는 경우, 왼쪽에 배치하는 경우, 오른쪽에 배치하는 경우를 구분하여 식을 세우는 것이었습니다.

 

사자를 배치하지 않는다면 모든 경우가 허용되기 때문에 기존의 경우의 수를 그대로 가져오게 되었고

 

왼쪽에 배치한다면 이미 왼쪽에 사자가 배치된 경우를 제외하고 배치가 가능하였습니다.

 

오른쪽도 동일하였구요 이렇게 구분하여 경우의 수를 구해보았고 그 결과를 보니 기존에 구한 결과와 동일하여 이게 논리적으로 좀더 올바른 점화식 이란것을 알 수 있었습니다.

 

어쩌다 보니 점화식을 찾아 문제를 빠르게 해결하였는데 논리적 점화식을 세운다고 전체 시간이 길어진 문제 였습니다.

 

그래도 점점 DP 문제를 해결하다 보니 DP 테이블을 설정하는 과정과 점화식을 보는 눈이 생겨 실력이 늘고 있다고 생각 되는것 같습니다.

 

점점 문제집을 다 풀어가서 다음번에도 문제집을 설정하여 계속해서 문제를 풀어 보겟습니다.