[백준] 9465번: 스티커

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

문제

알고리즘 접근 방법

DP를 이용한다.

선택한 스티커의 상 하 좌 우는 고를 수 없으므로, 어떤 스티커를 시작점으로 할 것인지 선택해야 한다.

스티커 판은 2xn의 크기이므로

1. 첫째 줄의 첫번째 칸에서 시작했을 때 얻을 수 있는 최대 점수
2. 둘째 줄의 첫번째 칸에서 시작했을 때 얻을 수 있는 최대 점수

두가지 경우로 나누어 접근한다.

점수 배열 sticker 와 각 스티커의 최댓값을 저장한 배열 dp가 있다고 하자.
이 때 dp[2][n+1] 로 생성하여 대각선 값이 없는 경우를 생각해
(1, 2번째 칸에서 시작하는 경우는 1, 2번째 전 대각선 값이 없는 경우가 있다)

dp[0][0] 과 dp[0][1] 은 0으로

dp[1][0] = sticker[1][0]
dp[1][1] = sticker[1][1] 로

초기화해준다.

선택한 스티커에서는 상하좌우를 고르지 못하기 때문에,
해당 스티커에서 얻을 수 있는 최대 점수는

1. 1번째 대각선 전에서 왔을 때
2. 2번째 대각선 전에서 왔을 때
   (3번째 이상부터는 1번째 * 3번 하는 경우가 더 점수가 많으므로 PASS)

로 나눌 수 있는 데 이 중 최댓값과 해당 스티커 점수 을 더하면 된다.

이를 식으로 정하면 다음과 같다.

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

풀이

#include <iostream>
#include <algorithm>

using namespace std;


int main(){
    int T, n;

    cin >> T; // 테스트 케이스

    for (int i=0; i<T; i++){

        cin >> n; // 스티커 열 개수 입력 받기

        int sticker[2][n+1] = {0,}; // 각 숫자를 골랐을 때 최대 점수 
        int dp[2][n+1] = {0,}; // 각 숫자를 골랐을 때 최대 점수 

        for (int j=0; j<2; j++) // 스티커 점수 배열 입력 받기
            for(int k=1; k<=n; k++)
                cin >> sticker[j][k]; 

        dp[0][0] = dp[1][0] = 0; // 0번째 칸 초기화

        dp[0][1] = sticker[0][1];
        dp[1][1] = sticker[1][1];
    
        // 각 칸을 선택 했을 때, 1번째 대각선 전의 점수와 2번 대각선 전의 점수를 비교하여 최댓값을 더함
        
        for(int i=2; i<=n; i++){
            dp[0][i] = max(dp[1][i-2], dp[1][i-1]) + sticker[0][i];
            dp[1][i] = max(dp[0][i-2], dp[0][i-1]) + sticker[1][i];
        }
        int score = max(dp[0][n], dp[1][n]); // 점수

        cout << score << endl;
    }
    
    return 0;
}

정리

첨에 DP 안하고 완전 탐색으로 했다가 시간 초과 OMG ㅠㅠ
찾아봐도 잘 이해 못했는데 occidere님 블로그가 도움이 많이 되었당

💡 참고 포스팅

occidere님 블로그