https://www.acmicpc.net/problem/9465
문제
> 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다.
> 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다.
> 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.
> 상냥이가 구매한 스티커의 품질은 매우 좋지 않다.
> 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.
>즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.
> 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.
> 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다.
> 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오.
> 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.
> 위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다.
> 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.접근
DP를 사용하여 해결한다.
기준 점을 스티커 배열의 0,0 과 1,0으로 잡는다.
그래서 각각 dp(0,0)과 dp(1,0)은 자신의 점수이다.
스티커 0,1과 1,1은 각각 사방에 있지않은 대각선 상에 있는 스티커로 부터 올 수 있다. 따라서 각각 가능한 최대 점수는 dp(0,1)은 dp(1,0)에 0,1의 값을 더한 값이고, dp(1,1)은 dp(0,0)에 1,1의 값을 더한 값이다.
이 다음부터는 각각의 스티커들은 본인이 선택당하기 위해선
바로 그동안 지그재그로 대각선에 있는 스티커에서 온 경우와, 바로대각선에 있는 스티커의 좌측에 있는 스티커에서 건너뛰고 바로 온 경우 가있다.
즉 예를 들면 0,2를 보면 지그재그로 와서 바로 대각선에 있는 1,1에서 왔을 때와, 건너뛰어서 1,0에서 왔을 때 이렇게 두 개가 있다.
그래서 최고점수를 얻어야하므로 두 dp값중 max연산으로 큰 걸 고른 뒤 자신의 점수를 더해주면 자신의 dp값이 된다.
이렇게 쭉 가면 제일 끝 열에 있는 두 dp값은 지금까지 쌓인 최대들만 골라서 온 점수 들이다. 이 두 점수 중 또 큰 점수를 고르면 현 스티커에서 고를 수 있는 최고점수이다.
문제해결
> 테스트 케이스 수를 입력받고 그 만큼 반복한다.
> 열의 개수를 입력받고 매번 스티커의 점수를 새롭게 주기위해 스티커 점수를 담아놓을 벡터를 초기화 해준다.
> dp값도 초기화 해주며 기준이 될 0,0과 1,0에 대해 자신의 점수로 초기화 해주고
올 수 있는 경우가 하나 뿐인 0,1과 1,1에 대해서도 직접 처리해준다.
> 반복문으로 열의 수만큼 먼저 돌리고 그 안에서 두 줄이므로 행의 수만큼 돌린다.
> 이때, 0행에 있는 스티커는 대각선이 1행에 있는 스티커들이므로 j+1,i-1과 i-2로 따져준다.
1행은 대각선이 0행 뿐이므로 j-1, i-1과 i-2로 따져준다.
> 두 경우의 max연산을 한 뒤 나온 최대값에 자신의 점수를 더해 dp를 구해준다.
> 최종 열 까지 계산해 왔다면 두 값중 최대를 골라야 스티커 판에서 얻을 수 있는 최고점수이다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<vector<int>> sticker;
vector<vector<int>> dp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T, n;
cin >> T;
while (T--)
{
cin >> n;
sticker.assign(2, vector<int>(n));
for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) cin >> sticker[i][j];
dp.assign(2, vector<int>(n));
dp[0][0] = sticker[0][0];
dp[1][0] = sticker[1][0];
dp[0][1] = sticker[0][1] + dp[1][0];
dp[1][1] = sticker[1][1] + dp[0][0];
for (int i = 2; i < n; i++)
{
for (int j = 0; j < 2; j++)
{
if (j == 0) dp[j][i] = max(dp[j + 1][i - 1], dp[j + 1][i - 2]) + sticker[j][i];
else dp[j][i] = max(dp[j - 1][i - 1], dp[j - 1][i - 2]) + sticker[j][i];
}
}
cout << max(dp[0][n - 1], dp[1][n - 1]) << '\n';
}
}
후기
dp만 보면 그냥 한숨부터 나왔었는데 그동안 거꾸로 생각하기 류 dp들을 몇번 봐와서 그런지 딱 생김새가 그런 문제 같았다.
그래서 현 스티커까지의 최대값을 구하기 위해 어떤 스티커들을 타고타고 왔을 때 최대일까? 로 생각을 하며 규칙을 찾다가 올 수 있는게 대각선, 건너뛰고 대각선 두개 만 있다는걸 알았고 이를 이용해 구해보니 결과가 나왔다.
기분이 좋다.
