[백준 9465] 스티커

---

• 스티커 한 장을 때면 해당 스티커의 상, 하, 좌, 우에 해당하는 스티커를 사용할 수 없다.
• 스티커의 합이 최대가 되기 위해 스티커를 때는 방법을 구하라.
  

---

N제한이 100,000 인 경우이며 대략 경우의 수를 살펴보아도 2^N 정도 되는 복잡도이다. 전부다 땔 수 있는 경우는 아니지만 최대로 때어야 하기에

N은 클 수 밖에 없을 것이며, 완전 탐색으로는 힘들다

-> 따라서, 동적 계획으로 풀면 된다.

열 기준으로 보자.

N열일 때의 최댓값을 구해야 한다. 여기서 N열에 스티커를 땔 수 있는 방법은 3가지이다. 윗쪽을 때거나, 아랫쪽을 때거나, 안 때거나!

1. 안 땐 경우 ( 0 )

n - 1 열은 위, 아래 어디든 스티커를 땔 수 있다.

--> DP(n, 0) = MAX( DP(n-1, 0), DP(n-1, 1), DP(n-1, 2) )

2. 윗쪽을 땐 경우 ( 1 )

n - 1 열은 아래 스티커만 때야 한다.

--> DP(n, 1) = MAX( DP(n-1, 0), DP(n-1, 2) )

3. 아랫쪽을 땐 경우 ( 2 )

n - 1 열은 위쪽 스티커만 떄야 한다.

--> DP(n, 2) = MAX( DP(n-1, 0, DP(n-1, 1) )

0. 기저 사례 : N이 0보다 작은 경우, 방법이 없기에 return 0

int go(int n, int dir) {

if (n == -1) {

return 0;

}

int& ret = dp[n][dir];

if (ret != -1) return ret;

if (dir == 0) {

return ret = tripMax(go(n - 1, 0), go(n - 1, 1), go(n - 1, 2));

}

else if (dir == 1) {

return ret = a[0][n] + max(go(n - 1, 0), go(n - 1, 2));

}

else if (dir == 2) {

return ret = a[1][n] + max(go(n - 1, 0), go(n - 1, 1));

}

}

---

Review.

각 경우의 수를 잘 생각해보자, 그리고 기저 사례는 항상 중요!