백준 9465번

스티커

Posted by ChoiCube84 on August 21, 2023 · 6 mins read
프로그래밍 문제풀이

백준 9465번

오늘 풀어본 문제는 백준의 9465번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

상근이의 여동생 상냥이는 문방구에서 스티커 $2n$ 개를 구매했다. 스티커는 그림 (a)와 같이 $2$ 행 $n$ 열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

스티커

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, $2n$ 개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 $50$, $50$, $100$, $60$ 인 스티커를 고르면, 점수는 $260$ 이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 ($100$ 과 $70$)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 $n$ $(1 \leq n \leq 100,000)$ 이 주어진다. 다음 두 줄에는 $n$ 개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 $0$ 보다 크거나 같고, $100$ 보다 작거나 같은 정수이다.

출력

각 테스트 케이스 마다, $2n$ 개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

풀이과정

1번째 시도

이 문제를 처음 읽고 DP를 활용하는 문제라는 것을 알 수 있었다. 어떤 스티커를 떼었을 때 상하좌우에 있는 스티커를 못 쓰게 된다고 되어있는데, 스티커는 두 줄로 되어있기 때문에 실질적으로는 반대쪽 줄의 스티커와 양 옆의 스티커가 훼손된다고 생각할 수 있다.

그러면 각 열별로 스티커를 하나도 떼지 않았거나, 윗줄의 스티커를 떼었거나, 아랫줄의 스티커를 뗀 경우 총 3가지가 존재하고, 각 경우에 따라 점화식을 세울 수 있다.

  • 현재 열에서 스티커를 떼지 않은 경우의 최대 가치는 이전 열에서 3가지 경우 중 최대값을 선택한다.

  • 윗줄에서 스티커를 뗀 경우는 이전 열에서 스티커를 떼지 않았거나 아랫줄에서 스티커를 뗀 경우 중 최댓값을 선택하고 뗀 스티커의 가치와 더한다.

  • 아랫줄에서 스티커를 뗀 경우는 이전 열에서 스티커를 떼지 않았거나 윗줄에서 스티커를 뗀 경우 중 최댓값을 선택한고 뗀 스티커의 가치와 더한다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

int dp[3][100001] = { 0, };
int value[2][100001] = { 0, };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int T;
	cin >> T;

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

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

		for (int i = 1; i <= n; i++) {
			dp[0][i] = max({ dp[0][i - 1], dp[1][i - 1], dp[2][i - 1] }); // No sticker
			dp[1][i] = max(dp[0][i - 1], dp[2][i - 1]) + value[0][i]; // Up sticker
			dp[2][i] = max(dp[0][i - 1], dp[1][i - 1]) + value[1][i]; // Down sticker
		}

		cout << max({ dp[0][n], dp[1][n], dp[2][n] }) << "\n";
	}

	return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

오늘 이 문제를 풀면서 CLASS 4에 도달하게 되었다!

CLASS 4

CLASS 3 까지는 조금만 생각하면 금방금방 쉽게 풀리는 문제들이 많았지만, CLASS 4 부터는 문제의 난이도가 확 뛰는 것이 체감되었다. 그래도 매일 꾸준히 문제를 풀어나가니 이런 성과를 얻은 것 같다.

이제 다음 목표는 CLASS 4 에센셜을 취득하는 것이다. CLASS 4 아이콘도 좋지만, 역시 휘장이 없으니 허전한 것 같다. 내일도 열심히 달려봐야겠다.

오늘의 PS는 여기까지!

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

← Previous Post Next Post →