백준 9465 (스티커) c++

문제

9465번: 스티커

n열 2행에 해당하는 배열을 입력받고 왼쪽 부터 시작해서 스티커를 뽑습니다. 

스티커를 뽑으면 다음 스티커는 아까 뽑았던 위치에서 상하좌우 인접해 있으면 안됩니다.

스티커 점수를 최대로 뽑을 수 있는 점수를 구하는 문제입니다.

다음과 같은 경우 50 + 50 + 100 + 60 = 260입니다.

 

처음에 접근을 잘못하여 틀렸던 문제입니다. 

제가 처음에 접근한 방법은 dfs 형태로 접근하였습니다. 

그러다 보니 인접하지 않은 곳들을 탐색하다보니 중복된 탐색을 하게 되었습니다.

결국 시간초과가 발생하였습니다. 

 

검색의 힘을 빌려 dp로 해결하였습니다.

먼저 dp의 처음부분입니다.

dp[x][y]는 x행 y열의 부분을 선택했을 때 최대 스티커 점수입니다.  

dp[0][0] = arr[0][0] 입니다. 

당연히 처음 부분이니 무조건 선택해야 합니다.

마찬 가지로 dp[1][0] = arr[1][0] 입니다.

 

dp[0][1]은 무조건 dp[1][0] + arr[0][1] 입니다.

dp[1][1]도 마찬가지로 dp[0][0] + arr[1][1] 입니다.

 

dp[0][2]이 부터 점화식이 세워집니다.

다음과 같이 arr[0][2]를 뽑을 때 dp[1][1]을 뽑고 arr[0][2]를 뽑을 수 있습니다.

또 다른 경우는

dp[1][0]을 뽑고 arr[0][2]를 뽑을 수 있습니다. 

따라서 dp[1][1]과 dp[1][0]을 비교해 더 큰 수를 선택하고 arr[0][2]를 더해주면 dp[0][2]가 됩니다.

 

dp[1][2]의 경우도 마찬가지 입니다. 반대로 생각해주면 됩니다.

 

이제 점화식을 세워보면

dp[0][i] = max(dp[1][i-2], dp[1][i-1]) + arr[0][i]

dp[1][i] = max(dp[0][i-2], dp[0][i-1]) + arr[1][i] 입니다.

dp[0][0] = arr[0][0];
dp[1][0] = arr[1][0];
dp[0][1] = dp[1][0] + arr[0][1];
dp[1][1] = dp[0][0] + arr[1][1];
for (int i = 2; i < n; i++) {
	dp[0][i] = max(dp[1][i - 2], dp[1][i - 1]) + arr[0][i];
	dp[1][i] = max(dp[0][i - 2], dp[0][i - 1]) + arr[1][i];
}
cout << max(dp[0][n - 1], dp[1][n - 1]) << '\n';

---

전체 코드 입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[2][100001];
int dp[2][100001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < n; j++)
                cin >> arr[i][j];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = arr[0][0];
        dp[1][0] = arr[1][0];
        dp[0][1] = dp[1][0] + arr[0][1];
        dp[1][1] = dp[0][0] + arr[1][1];
        for (int i = 2; i < n; i++) {
            dp[0][i] = max(dp[1][i - 2], dp[1][i - 1]) + arr[0][i];
            dp[1][i] = max(dp[0][i - 2], dp[0][i - 1]) + arr[1][i];
        }
        cout << max(dp[0][n - 1], dp[1][n - 1]) << '\n';
 
    }
    
    
    return 0;
}