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) 좌표에서 움직일 수 있는 경우의 수는 다음과 같다.
이렇게 두가지 방향으로 움직일 수 있는데 지금까지 풀었던 규칙을 찾는 경우의 다이나믹 프로그래밍 방법으로는 해당 좌표 기준으로 역으로 생각하는 방법을 써야 최종적으로 cache 배열의 마지막에 최대 값이 주어지는 것을 알 수 있다.
위의 그림의 경우를 보도록 하자.
값이 7인 해당 좌표가 선택되는 경우의 수는 주황색 선으로 이어져 있는 스티커로부터 올 수 있다. 이때, 각 주황색 선으로 이어진 스티커 중 더 큰 값을 선택하여 더하면 해당 좌표에서는 최대 값을 얻을 수 있는 것이다.
그렇기 때문에 우리는 다음과 같은 점화식을 얻을 수 있다.
이렇게 해서 최종적으로 둘 중 더 큰 것이 정답이 된다.
#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번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
백준 9935 - 문자열 폭발(C++) (0) | 2023.06.10 |
---|---|
백준 9663 - N-Queen(C++) (0) | 2023.06.06 |
백준 9251 - LCS(C++) (2) | 2023.06.05 |
백준 5639 - 이진 검색 트리(C++) (0) | 2023.06.04 |
백준 2638 - 치즈(C++) (0) | 2023.06.04 |