[C++] 백준 9465: 스티커

안녕하세요 오늘 풀어볼 문제는 스티커 입니다.

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

 

스티커는 dp 문제인데 기본 DFS에 결합한 형태와는 조금 다른 문제에요.

단순히 2차원 배열을 탐색하며 재귀 호출하는 방식이 아니고 점화식을 정의해줘야 합니다.

---

점화식을 정의하기 위해 문제를 개념적으로 뜯어보겠습니다.

우선 스티커의 1~n번째 열을 순차로 탐색하는 걸 전제로 할게요.

그리고 지금 k번째 열을 고려하고 있다고 가정할게요.

보라색 네모 부분이 k번째 열입니다.

이 때 고려할 수 있는 경우의 가짓수는 3가지입니다.

1. (k열 0행)을 선택한다.

2. (k열 1행)을 선택한다.

3. 해당 스티커를 선택하지 않는다.

 

각 경우들의 동작은 잠시 미뤄두고 이번엔 k + 1번째 열을 고려해볼게요.

초록색으로 체크한 부분이 선택한 스티커입니다.

각각 0행과 1행 스티커를 선택한 경우입니다.

이 경우들에서 '반드시 이전 열에서 선택한 행과 다른 행을 선택'해야 한다는 걸 알 수 있습니다.

(k + 1열 0행) 스티커를 선택하려면 k열에서는 1행의 스티커를 선택해야 겠네요.

 

네, 위에서 고려한

1. (k열 0행)을 선택한다.

2. (k열 1행)을 선택한다.

이 두 경우들이 동작했습니다.

 

그럼

3. 해당 스티커를 선택하지 않는다.

이 경우는 어떻게 생각해야 할까요?

 

정답은 (k - 1열 선택한 스티커와 다른 행)의 스티커를 선택하는 것입니다.

이 경우일 때 k열의 어떠한 스티커도 선택하지 않으면서 가장 높은 점수를 가져올 수 있네요.

 

그런데 이런 의문이 생길 수 있습니다.

'같은 행의 스티커를 가져오면 안될까?'

직관적으로는 괜찮아 보이네요.

하지만 이 경우는 성립하지 않습니다.

 

왜냐하면 아래 경우에서 이미  (k열 0행)을 선택할 수 없어졌기 때문입니다.

(k - 1열 0행)을 선택 했을 때 (k열 0행)은 경우에서 배제하기 때문에 '고르지 않는다'는 경우도 존재할 수 없는 거죠.

 

음... 제 설명이 도움이 되고 있으면 좋겠네요.

---

위 설명을 바탕으로 dp 배열을 정의한다면 아래와 같습니다.

 

• dp[0][i]: i번째 열의 위쪽 스티커를 선택했을 때의 최대 점수
• dp[1][i]: i번째 열의 아래쪽 스티커를 선택했을 때의 최대 점수

정의를 코드(점화식)으로 나타내면 아래와 같구요,

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

 

i - 1번째 열을 '선택하는 경우'와 '선택하지 않는 경우' 중 큰 점수를 고르는 개념을 아시겠나요?

 

이제 이 점화식을 반복문에서 돌리면 되는데, i - 2 인덱스를 사용하는 부분이 보이실 거에요,

0번열과 1번열은 초기화를 해줘야 한다는 뜻입니다.

dp[0][0] = stkr[0][0];
dp[1][0] = stkr[1][0];
dp[0][1] = dp[1][0] + stkr[0][1];
dp[1][1] = dp[0][0] + stkr[1][1];

---

아래는 코드 전문

#include <iostream>
using namespace std;

int T, n;
int stkr[3][100001];
int dp[3][100001];

int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);

	cin >> T;

	while (T--) {
		cin >> n;

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

		dp[0][0] = stkr[0][0];
		dp[1][0] = stkr[1][0];
		dp[0][1] = dp[1][0] + stkr[0][1];
		dp[1][1] = dp[0][0] + stkr[1][1];

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

		cout << max(dp[0][n - 1], dp[1][n - 1]) << '\n';
	}
}

 

도움이 되셨다면 공감과 댓글 부탁드립니다.