JOI 2017/2018 Spring Training Camp Day1 3번 - Tents 풀이

[JOI 2017/2018 Spring Training Camp Day1 3번 - Tents]

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

17682번: Tents

 

[Subtask 1] $1 \leq H \leq 300$, $1 \leq W \leq 300$ (48점)

세제곱 풀이를 떠올려봅시다. 행과 열 둘 중 하나를 기준으로 잡고 시작하는데, 여기서는 행을 기준으로 떠올려봅시다. 위에서 아래로 한 행씩 내려갈 때마다 다음 정보들을 기억하고 있어야 합니다.

• 앞으로 남은 행의 개수는 몇 개인가?
• 사용할 수 있는 열 개수는 총 몇 개인가?
• S만 놓여있는 열은 몇 개인가?

세 번째 정보를 기억해야 하는 이유는, S만 놓여있는 열의 행 밑으로 N 한 개를 넣을 수도 있기 때문입니다.
이상에서 다음과 같이 dp식을 정의해봅시다.

• $ \textrm{dp} [i][j][k]$ : 현재 남아있는 행이 $i$개, 열이 $j$개이고, S만 놓여있는 열이 $k$개일 때, 텐트를 놓을 수 있는 총 경우의 수

 
한 행에 대하여 텐트를 놓을 수 있는 경우는 다음과 같습니다.

1. 아무 텐트도 놓지 않음
2. 남아있는 열 중 하나에 S 텐트를 놓음
3. 남아있는 열 중 하나에 N 텐트를 놓음
4. E 또는 W 텐트를 하나 놓음
5. E W 텐트 세트를 놓음

1. 아무 텐트도 놓지 않음
행만 하나 줄어들게 됩니다. 따라서 이 값은 $ \textrm{dp} [i-1][j][k]$ 값과 같습니다.
 
2. 남아있는 열 중 하나에 S 텐트를 놓음
사용할 수 있는 열 개수가 하나 줄어들고, 이 열에는 S텐트만 놓게 되므로 $k$가 증가하게 됩니다. 따라서 이 값은 $j \times \textrm{dp} [i-1][j-1][k+1]$과 같습니다.
 
3. 남아있는 열 중 하나에 N 텐트를 놓음
N 텐트는 S텐트만 놓여있는 열의 밑에 놓거나, 아무것도 놓여있지 않은 열에 놓을 수 있습니다.
전자의 경우 S텐트만 놓여있는 열의 개수가 $k$이고, 이는 $j$값을 건드리지 않기 때문에 $k \times \textrm{dp} [i-1][j][k-1]$과 같습니다. 후자의 경우 $j$의 개수가 하나 줄어들기 때문에 $j \times \textrm{dp} [i-1][j-1][k]$와 같습니다.
 
4. E 또는 W 텐트를 하나 놓음
남아있는 열 아무 곳에 텐트를 하나 놓으면 됩니다. E 또는 W 두 가지 경우이므로 $2j \times \textrm{dp} [i-1][j-1][k]$와 같습니다.
 
5. E W 텐트 세트를 놓음
남아있는 열들 중 2개를 선택한 뒤 E W를 차례로 배치하면 됩니다. 따라서 이 값은 $ _{j}\textrm{C}_{2} \times \textrm{dp} [i-1][j-2][k]$와 같습니다.
 
 

 

 

[Subtask 2] $1 \leq H \leq 3000$, $1 \leq W \leq 3000$ (52점)

세제곱 풀이를 제곱 풀이로 바꿀 수 있을까요? 바꿀 수 있다면 위의 $i$, $j$, $k$ 중 어떤 정보를 버릴 수 있을까요?
$i$, $j$는 행과 열에 관한 직접적인 정보를 제공하므로 그대로 두고, $k$를 들여다봅시다. 한 행의 어떤 열에 S텐트를 둔다고 했을 때, 동시에 그 밑의 행의 같은 열에 N텐트를 둘지의 여부를 동시에 결정한다고 해봅시다. 다음과 같이 경우들을 나눠볼 수 있습니다.

1. 아무 텐트도 놓지 않음
2. E, W, S, N 텐트 하나를 놓음
3. 이 행 남은 열에 S를 두고 아래 남은 행의 같은 열에 N텐트를 놓음
4. E W 텐트 세트를 놓음

 
이제 $k$ 정보는 필요하지 않으므로, dp식을 다음과 같이 재정의해봅시다.

• $ \textrm{dp} [i][j]$ : 현재 남아있는 행이 $i$개, 열이 $j$개일 때, 텐트를 놓을 수 있는 총 경우의 수

 
1. 아무 텐트도 놓지 않음
행만 하나 줄어들게 됩니다. 따라서 이 값은 $ \textrm{dp} [i-1][j]$ 값과 같습니다.
 
2. 남아있는 열 중 하나에 E, W, S, N 텐트 하나를 놓음
사용할 수 있는 열 개수가 하나 줄어들고 방향 각각의 경우의 값이 $j \times \textrm{dp} [i-1][j-1]$이고 방향 가짓수가 4개이므로 $4j \times \textrm{dp} [i-1][j-1]$로 나타낼 수 있습니다.
 
3. 남아있는 열 중 하나에 S텐트를 두고, 아래 남아있는 행의 같은 열에 N 텐트를 놓음
S텐트를 두는 경우의 수는 $j$이고, 이 행에는 이미 텐트를 두었으므로 N텐트를 둘 수 있는 가능한 행의 개수는 $i-1$개입니다. 총 2개 행을 사용하였으므로 이 값은 $(i-1) \times j \times \textrm{dp} [i-2][j-1]$과 같습니다.
 
4. E W 텐트 세트를 놓음
남아있는 열들 중 2개를 선택한 뒤 E W를 차례로 배치하면 됩니다. 따라서 이 값은 $_{j}\textrm{C}_{2} \times \textrm{dp}[i-1][j-2]$와 같습니다.