[BOJ] 9465번 스티커

문제 바로가기

접근

행의 길이가 2로 고정되어 있기 때문에 다음과 같이 2가지 경우로 나누어 점화식을 만들 수 있다. 대각선 지점에 있는 가장 가까운 칸과 그 다음으로 가까운 칸이다.

그러면 그 뒤의 칸은 보지 않아도 되는지 보면, 3칸 떨어진 1->8로 갈 경우에는 1->4->5->8의 경우가 커버하고 있음을 확인할 수 있다.

위의 관찰로 점화식을 세우면 다음과 같다.
dp[0][i] = max(dp[1][i-1], dpdp[1][i-2]) + arr[0][i]
dp[1][i] = max(dp[0][i-1], dpdp[0][i-2]) arr[1][i]

1. 시간초과가 났던 DFS 풀이

#include <iostream>
#include <cstring>
using namespace std;

int t, n, max_score;
int nx, ny;
bool flag;
int tmp;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int stickers[2][100000];
bool visited[2][100000];

void dfs(int score) {
  max_score = max(max_score, score);

  for(int x = 0; x < 2; x++) {
    for(int y = 0; y < n; y++) {
      if(!visited[x][y]) {
        flag = true;
        for(int z = 0; z < 4; z++) {
          nx = x + dx[z];
          ny = y + dy[z];
          if(-1 < nx && nx < 2 && -1 < ny && ny < n && visited[nx][ny])
            flag = false;
        }
        if(flag) {
          visited[x][y] = true;
          dfs(score + stickers[x][y]);
          visited[x][y] = false;
        }
      }
    }
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  cin >> t;
  for(int i = 0; i < t; i++) {
    cin >> n;
    memset(stickers, 0, sizeof(stickers));
    memset(visited, false, sizeof(visited));
    max_score = 0;
    for(int x = 0; x < 2; x++) {
      for(int y = 0; y < n; y++) {
        cin >> stickers[x][y];
      }
    }
    dfs(0);
    printf("%d\n", max_score);
  }
}

2. 점화식으로 통과한 풀이

#include <iostream>
#include <cstring>
using namespace std;

int t, n;
int stickers[2][100000];
int dp[2][100000];

int main() {
  std::ios::sync_with_stdio(false);
  cin >> t;
  for(int i = 0; i < t; i++) {
    cin >> n;
    memset(stickers, 0, sizeof(stickers));
    memset(dp, 0, sizeof(dp));
    for(int x = 0; x < 2; x++) {
      for(int y = 0; y < n; y++)
        cin >> stickers[x][y];
    }

    dp[0][0] = stickers[0][0];
    dp[1][0] = stickers[1][0];
    dp[0][1] = dp[1][0] + stickers[0][1];
    dp[1][1] = dp[0][0] + stickers[1][1];
    for(int j = 2; j < n; j++) {
      dp[0][j] = max(dp[1][j - 1], dp[1][j - 2]) + stickers[0][j];
      dp[1][j] = max(dp[0][j - 1], dp[0][j - 2]) + stickers[1][j];
    }
    printf("%d\n", max(dp[0][n - 1], dp[1][n - 1]));
  }
}