[C++] 백준 10476번 좁은 미술전시관

문제

기다랗고 2N개의 방이 있는 미술관이 있다. 미술관은 세로로 N줄, 가로로 2칸의 방으로 구성된다. 위아래, 양 옆으로 붙어있는 방들은 서로 연결되어 있다. 오늘의 큐레이터는 미술관 운영진으로부터 비용 절감을 위해 k개의 방을 닫아야 한다는 통보를 받았다. 방문자들은 한쪽 끝의 두 방중 적어도 한 방에는 방문할 수 있어야 하며 다른쪽 끝의 두 방중 한 방으로 나갈 수 있어야 한다. 즉, 큐레이터는 같은 줄의 어느 두 방을 모두 닫거나 대각선으로 붙어있는 두 방을 닫아서는 안 된다는 뜻이다. 또한, 각 방들이 대중에게 공개되었을 때 얼마나 큰 가치를 지니는지를 큐레이터는 알고 있다. 큐레이터는 위 조건과 같이 방문자들의 길을 막지 않으면서 방문자들에게 공개 가능한 가치의 합을 최대로 하고 싶어한다.

입력

입력은 여러 갤러리들로 구성된다. 각각의 입력은 두 정수 N과 k(3 <= N <= 200, 0 <= k < N)로 구성되며 각각 미술관의 세로길이와 닫아야 하는 방의 수를 뜻한다. 이어지는 N줄에 걸쳐 각 줄에 두 개의 정수가 입력되며, 각 줄에 존재하는 두 방의 가치를 뜻한다. 각 방의 가치 v는 0 이상 100 이하이다. 마지막 미술관의 정보 이후에는 두 개의 정수 0 0이 입력된다.

출력

각 갤러리에 대해서 한 줄에 걸쳐 대중에게 공개될 수 있는 가치의 최대합을 출력한다.

풀이

solve 함수는 현재 line번째 줄이고 닫아야할 방의 수가 toClose이고 바로 윗줄의 방 상태가 state일때 가치의 최대합을 리턴하는 함수이다. 현재줄의 방의 열고 닫음 여부를 결정할때 바로 윗줄의 상태에서 영향을 받으므로 윗줄의 왼쪽방이 닫힌 0, 오른쪽방이 닫힌 1, 둘다 열린 2의 3가지 상태만 알고있으면 된다.
state가 0일 경우 오른쪽 방을 닫을 수 없고, 1일 경우 왼쪽 방을 닫을 수 없다. state가 2라면 모든 경우가 다 가능하다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n,k;
int room[200][2];
int dp[200][201][3];

int rsum(int line){
  int total = 0;
  for (int i=line; i<n; i++)
    for (int j=0; j<2; j++)
      total += room[i][j];

  return total;
}

// 왼쪽 닫힘 0, 오른쪽 닫힘 1, 둘다 열림 2
int solve(int line, int toClose, int state){
  if (toClose == 0) return rsum(line);
  if (line == n) return -40000;

  int& ret = dp[line][toClose][state];
  if (ret != -1) return ret;
  ret = -40000;

  if (state != 1) ret = max(ret, solve(line+1,toClose-1,0)+room[line][1]);
  if (state != 0) ret = max(ret, solve(line+1,toClose-1,1)+room[line][0]);
  ret = max(ret, solve(line+1,toClose,2)+room[line][0]+room[line][1]);

  return ret;
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  ifstream cin;
  cin.open("input.txt");

  cin >> n >> k;

  for (int i=0; i<n; i++)
    for (int j=0; j<2; j++)
      cin >> room[i][j];

  memset(dp, -1, sizeof(dp));

  cout << solve(0,k,2);
}