Ray`s Tech Lab

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

0마리를 배치하는 것도 가능하고, 가로 세로로 붙지 않도록 배치해야 하므로 이론상 N마리까지 배치가능하다.

1. 브루트한 방법으로 풀이

직접 0 ~ N마리의 사자들을 하나하나 배치하는 방법이 있는데, 이 방법은 러프하게 생각하면 2^2n번 정도의 연산을 하게 될텐데 n은 100,000까지 주어질 수 있으므로 시간 내에 통과할 수 없을 것이다.

그렇다면 DP나 그리디를 통한 방법을 의심헤야 한다.

2. 우선 부분문제로 쪼갤 수 있는가?

쪼갤 수 있다. K마리(K <= N)의 사자를 배치한다고 할 때

1) 첫 사자를 첫째 줄 왼쪽 칸에 배치하는 경우

2) 첫 사자를 첫째 줄 오른쪽 칸에 배치하는 경우

3) 첫 사자를 첫째 줄에 배치하지 않는 경우

로 쪼갤 수 있다.

3. 그럼 중복되는 구조가 있는가? 있다면 DP로 풀이가 가능할 것이다.

중복되는 구조 역시 있다. N개의 행에 사자 K마리를 배치한다 할 때

첫 사자를 첫 줄 왼쪽에 배치할 땐 두 번째 사자를 다음 줄의 오른쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

첫 사자를 첫 줄 오른쪽에 배치할 땐 두 번째 사자를 다음 줄의 왼쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

첫 사자를 첫 줄에 배치하지 않을 땐 두 번째 사자를 그 줄의 왼쪽 또는 오른쪽에 배치하거나 아예 그 줄에 배치를 안 하거나

정리하자면

f(N, K, left)를 N개의 행에 사자 K마리를 배치하는데 첫 줄 왼쪽에 사자를 두는 경우

f(N, K, right)를 N개의 행에 사자 K마리를 배치하는데 첫 줄 오른쪽에 사자를 두는 경우

f(N, K, no)를 N개의 행에 사자 K마리를 배치하는데 첫 줄에 사자를 두지 않는 경우라고 한다면

f(N, K, left) = f(N-1, K-1, right) + f(N-1, K-1, no)f(N, K, right) = f(N-1, K-1, left) + f(N-1, K-1, no)f(N, K, no) = f(N-1, K, left) + f(N-1, K, right) + f(N-1, K, no)이라는 관계를 구할 수 있고, 중복되는 케이스들을 관찰가능하다.

4. 점화식을 세워보자

사실 점화식은 위에서 이미 세웠다. dp[i][j][k]라는 배열을 만들어서 그대로 적용라면 되며, 최종적으론 dp[N][0] ~ dp[N][N]까지를 합치면 그것이 답이 될 것이다.그러나 문제가 있다. 저 식 그대로 DP배열을 만들어서 사용하자면 3차원 배열이 만들어지는데, N은 최대 10만이고 K도 N까지의 범위를 가지니 10만 X 10만 X 3 = 3백억의 크기를 갖는 배열이 만들어지고 이는 메모리 제한에 걸릴 것이다..여기서 막혔고, 많은 고민을 하다가 다른 분들이 푼 걸 참고하게 됐다..

위의 점화식은 "몇 마리의 사자를 배치하는가"에도 중점이 있는 점화식이며, 첫 줄의 왼쪽에 배치하는 경우와 오른쪽에 배치하는 경우 그리고 첫 줄에 배치를 하지 않는 경우라는 3가지 케이스로 쪼개어 경우의 수들을 관리한다. 그러나 X개의 행에서 K마리의 사자를 배치하는 여러 방법들이 있다고 할 때, 행의 수 X만 같다면 그 방법들 모두 한꺼번에 묶어서 첫 줄의 왼쪽/오른쪽에 배치하는 경우와 첫 줄에 배치하지 않는 경우라는 3가지 케이스로 분류할 수 있다. 행의 수만 같다면 마리 별로 배치하는 방법까진 고려하지 않아도 되는 것.

즉 dp[x]를 x개의 행(즉 2*x칸의 우리)에 사자들을 배치하는 방법이라 하면, dp[x] = dp[x][left] + dp[x][right] + dp[x][no]라는 3가지 케이스로 보는 게 더 편하다는 것임 

이렇게하면 점화식이 훨씬 쉬워진다.

dp[N][left] = dp[N-1][right] + dp[N-1][no]

dp[N][right] = dp[N-1][left] + dp[N-1][no]

dp[N][no] = dp[N-1][left] + dp[N-1][right] +dp[N-1][no]

N = int(input())

mod = 9901

dp = [[0, 0, 0] for _ in range(N + 1)]
dp[1] = [1, 1, 1]

for i in range(2, N + 1):
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % mod
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod

print(sum(dp[N]) % mod)

느끼고, 배운 점

이 문제의 난이도가 실버1에 불과하단 걸 알고 현타가 왔다. 다른 사람들은 쉽게 생각하는 걸 나는 어렵게 생각했구나..라면서,, 

직관적으로 N=1일때의 배치방법, N=2일때의 배치방법들을 써가면서 규칙을 찾아 쉽게 푸는 방법도 있었다. 그래도 내가 한 방법이 잘못됐다고는 생각하지 않는다. 나만의 푸는 패턴을 만들어가며 연습하면서 감각을 길러가고, 실전에선 그 감각을 토대로 직관적으로(브루트하게 풀 수 있는지 없는지 따지고 그런 과정 없이) 풀 수 있을 거라고 생각한다..

배운 점은 글쎄..잘 모르겠다. 경험만이 살 길이란 생각이 들던 문제.