백준 9465 - 스티커(C++)

문제

2•N의 배열이 주어진다. 이 배열의 요소 안에는 각각의 값어치를 나타내는 값이 주어진다.

 

이때, 한 요소와 변을 공유하는 요소는 사용하지 못할 때 사용할 수 있는 요소를 이용하여 최대 값을 구하는 문제이다.

 

즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커의 집합을 구하는 문제이다.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

 

각 테스트 케이스의 첫째 줄에는 N이 주어진다. (1 ≤ N ≤ 100,000)

 

다음 두 줄에는 N개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다.

 

예제 입력

2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

 

예제 출력

260
290

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

우선 주어지는 입력에 비해 만들어질 수 있는 스티커의 조합의 수가 너무나도 많다.

 

또한, 해당 스티커가 중복적으로 나타날 수 있는 환경에서는 이 문제는 다이나믹 프로그래밍으로 풀어야 한다는 것을 알 수 있다.

 

우선 해당 위치에서 다음 스티커로 넘어가는 규칙을 찾아보도록 하자.

 

우선 문제에서 주어진 힌트로는 변을 공유하는 스티커는 이용할 수 없다는 것이다. 즉, 다음과 같이 나타낼 수 있다.

 

우선 위의 그림을 보게 되면 (0,0) 좌표에서 움직일 수 있는 경우의 수는 다음과 같다.

1. 대각선으로 움직인다. 5 -> 5
2. 대각선 + 1로 움직인다. 5 -> 7

이렇게 두가지 방향으로 움직일 수 있는데 지금까지 풀었던 규칙을 찾는 경우의 다이나믹 프로그래밍 방법으로는 해당 좌표 기준으로 역으로 생각하는 방법을 써야 최종적으로 cache 배열의 마지막에 최대 값이 주어지는 것을 알 수 있다.

 

위의 그림의 경우를 보도록 하자.

 

값이 7인 해당 좌표가 선택되는 경우의 수는 주황색 선으로 이어져 있는 스티커로부터 올 수 있다. 이때, 각 주황색 선으로 이어진 스티커 중 더 큰 값을 선택하여 더하면 해당 좌표에서는 최대 값을 얻을 수 있는 것이다.

 

그렇기 때문에 우리는 다음과 같은 점화식을 얻을 수 있다.

• dist[0][i] = std::max(dist[1][i - 2], dist[1][i - 1]) + board[0][i];
• dist[1][i] = std::max(dist[0][i - 2], dist[0][i - 1]) + board[1][i];

이렇게 해서 최종적으로 둘 중 더 큰 것이 정답이 된다.

• ret = std::max(dist[0][N - 1], dist[1][N - 1]);

코드

#include <iostream>
#include <cstring>

int board[2][100001];
int cache[2][100001];

int solve(int N)
{
	cache[0][0] = board[0][0];
	cache[1][0] = board[1][0];
	cache[0][1] = board[0][1] + cache[1][0];
	cache[1][1] = board[1][1] + cache[0][0];
	for (int i = 2; i < N; i++)
	{
		cache[0][i] = board[0][i] + std::max(cache[1][i - 1], cache[1][i - 2]);
		cache[1][i] = board[1][i] + std::max(cache[0][i - 1], cache[0][i - 2]);
	}
	return std::max(cache[0][N - 1], cache[1][N - 1]);
}

int main(void)
{
	int T;
	std::cin >> T;
	for (int i = 0; i < T; i++)
	{
		int N;
		std::cin >> N;
		std::memset(board, 0, sizeof(board));
		std::memset(cache, 0, sizeof(cache));
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < N; j++)
				std::cin >> board[i][j];
		}
		std::cout << solve(N) << std::endl;
	}
	return 0;
}

문제 출처

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

9465번: 스티커