10476번 좁은 미술관

문제 설명

이번 문제는 가로로 두칸 세로로 N칸이 있는 미술관에서 각 방마다 가치가 정해져 있을 때, 아래 규칙대로 K개의 방을 닫아서 공개된 방의 가치의 합을 최대로 하는 경우를 구하는 문제입니다.

• 한쪽 끝의 두 방중 적어도 한 방에는 방문할 수 있어야 하고 다른 쪽 끝의 두 방중 한 방으로 나갈 수 있어야 한다.
• 즉, 같은 줄의 두 방을 모두 닫거나 대각선으로 붙어있는 두 방을 닫아서는 안 된다.

 

 

문제 풀이

아이디어

한 줄을 닫을 수 있는 방법의 수

한 줄에 있는 두 방을 모두 동시에 닫을 수 없으므로, 한 줄을 닫는 방법은 아래와 같습니다.

• 왼쪽만 닫는다
• 오른쪽만 닫는다
• 모두 열어 둔다

위와 같이 3가지 경우만 있습니다.

 

최대값을 구하는 방법

위에서부터 닫을 방을 정할 때, 현재 위치에서 각 방법에 대한 최대값을 구하는 방법으로 다이나믹 프로그래밍을 사용해보겠습니다.

 

풀이

다이나믹 프로그래밍

dp[n][k][i]로 다이나믹 프로그래밍을 이어나갈 때 각 원소는 다음을 나타냅니다.

n = 미술관의 행의 번호

k = 닫힌 방문의 개수

i = 한 줄을 닫을 수 있는 방법 ( i=0: 왼쪽만 닫음, i=1: 오른쪽만 닫음, i=2: 모두 열어둠)

 

그러므로, dp[n][k][i]는 다음과 같이 정의할 수 있습니다.

dp[n][k][i] = n번째 행까지 문을 닫은 개수가 k개일 경우 가치의 총합의 최대값

 

점화식

(room은 각 방의 가치를 담은 배열입니다.)

 

dp[n][k][0] = max( dp[n-1][k-1][0], dp[n-1][k-1][2] ) + room[n][1]

• n-1번째에서는 왼쪽만 닫았거나 둘 다 열려 있는 경우만 n번째 행의 왼쪽을 닫을 수 있습니다.
• n-1번째 행까지 k-1개의 방문을 닫았을 때 왼쪽만 닫힌 경우와 두 개 다 열린 경우의 최대값과 n번째 행의 오른쪽 방의 가치를 더해주면 n번째 행까지 k개의 방문을 닫고 왼쪽 방을 닫았을 경우의 최대값을 구할 수 있습니다.

 

dp[n][k][1] = max( dp[n-1][k-1][1], dp[n-1][k-1][2] ) + room[n][0]

• n-1번째에서는 오른쪽만 닫았거나 둘 다 열려 있는 경우만 n번째 행의 오른쪽을 닫을 수 있습니다.
• n-1번째 행까지 k-1개의 방문을 닫았을 때 오른쪽만 닫힌 경우와 두 개 다 열린 경우의 최대값과 n번째 행의 왼쪽 방의 가치를 더해주면 n번째 행까지 k개의 방문을 닫고 오른쪽 방을 닫았을 경우의 최대값을 구할 수 있습니다.

 

dp[n][k][2] = max( max( dp[n-1][k-1][0], dp[n-1][k-1][1] ), dp[n-1][k-1][2] ) + room[n][0] + room[n][1]

• n-1번째행에서 어떤 방을 닫았는지에 상관없이 모든 방을 열어둘 수 있으므로, dp[n-1][k-1]의 모든 원소 중 최대값에 n번째 행의 모든 방의 가치를 더해주면 됩니다.
• 단, k == n인 경우는 위의 점화식을 실행하면 안됩니다.
  (한 행에서 최대로 닫을 수 있는 방의 개수는 1개입니다. n번째 행을 모두 열었을 경우 닫을 수 있는 최대 방의 개수는 n-1입니다. 그러므로, k==n일 때 n번째 행의 모든 방을 열어둘 수 없습니다.)

 

그 다음, dp[N-1][K]의 원소 중 최대값을 출력하면 됩니다.

 

 

 

해결

처음에 방의 가치 순서대로 정렬을 가치가 최소인 방문을 닫는 식으로 진행하려다가 뒤늦게 DP를 생각해내서 오래 걸렸던 문제입니다...

 

문제 링크 : https://www.acmicpc.net/problem/10476

10476번: 좁은 미술전시관

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/10476.py