[백준/Baekjoon] 9465 스티커 C++ :: Dynamic Programming

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

9465번: 스티커

---

1. Logic

- 스티커를 뜯으면 상하좌우 한개씩은 무조건 못사용하기 때문에 함수를 작성할때 이전에 어떤 스티커를 골랐는지, 어디 위치에 있는 스티커를 골랐는지 넘겨준다

DP table[어떤 스티커를 골랐는지][스티커의 index] 

0 : 스티커를 안고르고 지나침

1 : 스티커의 y값이 0인 스티커를 선택

2 : 스티커의 y값이 1인 스티커를 선택

 

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int t, n;

vector<vector<int>> vec(2, vector<int>(100001, 0));
int dp[3][100001];

int solve(int prevSelect, int idx) {
    if(idx == n) return 0;
    int &ret = dp[prevSelect][idx];
    if (ret != -1)
        return ret;

    ret = 0;
    
    if (prevSelect == 0) {
        ret = max(ret, solve(1, idx + 1) + vec[0][idx]);
        ret = max(ret, solve(2, idx + 1) + vec[1][idx]);
    }
    else if(prevSelect == 1) {
        ret = max(ret, solve(2, idx + 1) + vec[1][idx]);
        ret = max(ret, solve(0, idx + 1));
    }
    else if(prevSelect == 2) {
        ret = max(ret, solve(1, idx + 1) + vec[0][idx]);
        ret = max(ret, solve(0, idx + 1));
    }
    

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> t;

    while (t--) {
        memset(dp, -1, sizeof(dp));
        cin >> n;

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

        cout << solve(0, 0) << "\n";
    }
}

 

 

---

 

 

3. Feedback

이번 문제를 풀대 가장 처음에 선택할 스티커에 대한 기준을 틀리게 세웠다.

 

처음 함수에 들어가게 되면 스티커를 0,0 에서 고를 수도 있고 안고를 수도 있는데, 내가 처음 짠 코드는 아예 처음부터 고르고 시작했다. 그리고 그 다음배열로 넘어가게되면 또 똑같은 y축의 스티커를 고르게 되어 로직이 틀리게된다.,

 

값은 나왔지만 다른 테스트케이스에서는 틀릴수도 있으니 엣지케이스들을 생각하는 것 또한 중요할 것 같다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐