Baekjoon 9465번 스티커

문제

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

걸린 시간

03 : 00 : 43 실패

시간 초과 풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int plate[2][100001], visited[2][100001], cache[2][100001];

int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int dp(int r, int c){ // row, col
    // 기저 사례
    if(c == n)    
        return 0;
    // 메모이제이션
    int& ret = cache[r][c];
    if(ret != -1)
        return ret;
    // 재귀 호출
    for(int x = c+1; x <= n; x++){
        for(int y = 0; y < 2; y++){
            if(!visited[y][x]){
                vector<pair<int, int>> tmp;
                for(int i = 0; i < 4; i++){
                    int ny = y+dy[i];
                    int nx = x+dx[i];
                    if(!visited[ny][nx] && 0 <= ny && ny < 2 && 1 <= nx && nx <= n){
                        visited[ny][nx] = 1;
                        tmp.push_back(make_pair(ny, nx));
                    }
                }
                visited[y][x] = 1;
                ret = max(ret, dp(y, x)+plate[y][x]);
                for(int i = 0; i < tmp.size(); i++)
                    visited[tmp[i].first][tmp[i].second] = 0;    
                visited[y][x] = 0;
            }
        }
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n;
        for(int i = 0; i < 2; i++)
            for(int j = 1; j <= n; j++)
                cin >> plate[i][j];
        memset(visited, 0, sizeof(visited));
        memset(cache, -1, sizeof(cache));
        cout << dp(0, 0) << "\n";
    }
    return 0;
}

규칙을 찾지 못해 모든 경우의 수에 메모이제이션을 적용한 풀이.

테스트 케이스의 개수와 반복문 속의 많은 연산으로 시간초과가 난 것으로 예상.

옳은 풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int plate[2][100001], cache[2][100001];

int dp(int y, int x){
    // 기저 사례
    if(x > n) return 0;
    if(x == n) return plate[y][x];
    // 메모이제이션
    int& ret = cache[y][x];
    if(ret != -1)
        return ret;
    // 재귀 호출
    ret = max(ret, dp((y+1)%2, x+1)+plate[y][x]);
    ret = max(ret, dp((y+1)%2, x+2)+plate[y][x]);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n;
        for(int i = 0; i < 2; i++)
            for(int j = 1; j <= n; j++)
                cin >> plate[i][j];
        memset(cache, -1, sizeof(cache));
        cout << max(dp(0, 0), dp(1, 0)) << "\n";
    }
    return 0;
}

맨 처음 스티커부터 차례로 떼어낸다고 했을 때 가능한 경우는 한 칸 앞 대각선, 두 칸 앞 대각선뿐인 규칙을 찾아내면 쉽게 풀이할 수 있다.

아직까지 메모이제이션을 적용하는 실력이 부족해서 많은 시행착오를 겪고있다. 올바른 캐쉬의 형태는 원본 데이터와 대부분 같다는 점을 기억하자.