[Baekjoon]백준 9465 스티커(실버 1) - Python/C/C++

문제설명

예제

문제를 살펴보면 스티커를 떼어내는데, 스티커당 점수가 존재한다

그리고 해당 점수가 최대가 되도록 스티커를 떼어내야한다

이 문제를 보자말자 dp알고리즘으로 해결해야할 것 같은 느낌이 들었다

 

sticker[0][i]는 위쪽행, i번째 열의 점수를 저장하고 sticker[1][i]는 아래쪽 행, i번째 열의 점수를 저장한다

스티커와 닿아있는 면은 다 떼어지기 때문에 제일 점수가 높은 상황은 지그재그로 떼어내는 것이라 생각할 수 있지만

첫번째 예시의 경우 50 50 100 10 40 보다 50 50 100 60이 점수의 합이 더 크다

따라서 현재 열의 점수에 이전 열과 전전열에서 올 수 있는 최댓값을 더해 계산해야한다

해당 방식으로 계산하면 지그재그만 확인하는 것이 아니라 모든 가능한 선택 경로 중 최대값이 저장된다

파이썬 코드로 구현하면 다음과 같다

import sys

input = sys.stdin.readline

case = int(input())
for _ in range(case):
    sticker_num = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]
    
    if sticker_num == 1:
        print(max(sticker[0][0], sticker[1][0]))
        continue
    
    sticker[0][1] += sticker[1][0]
    sticker[1][1] += sticker[0][0]
    
    for i in range(2, sticker_num):
        sticker[0][i] += max(sticker[1][i-1], sticker[1][i-2])
        sticker[1][i] += max(sticker[0][i-1], sticker[0][i-2])
        
    print(max(sticker[0][sticker_num-1], sticker[1][sticker_num-1]))

여기서 주의할 점은 sticker_num이 1인 경우도 존재할 수 있기 때문에 이에 대한 처리 과정도 필요하다

같은 동작을 하는 C와 C++ 코드도 작성해보았는데 sticker_num == 1이 아니라 sticker_num > 1로 처리하였으며

dp 배열을 따로 선언하여 작성하였다

C언어 작성과정에서 실수가 존재하였을 가능성도 있으나, 파이썬과 동일한 코드로 작성하였더니 IndexError가 발생하여

dp 배열을 따로 선언하여 배열 index 실수 가능성은 줄이고 코드 가독성은 높였다

#include <stdio.h>

#define MAX 100000

int main() {
    int caseCount;
    scanf("%d", &caseCount);

    while(caseCount) {
        int sticker_num;
        int sticker[2][MAX];
        int dp[2][MAX];
        scanf("%d", &sticker_num);

        for(int i=0; i<2; i++) {
            for(int j=0; j<sticker_num; j++) {
                scanf("%d", &sticker[i][j]);
            }
        }

        dp[0][0] = sticker[0][0];
        dp[1][0] = sticker[1][0];

        if(sticker_num > 1) {
            dp[0][1] = sticker[0][1] + dp[1][0];
            dp[1][1] = sticker[1][1] + dp[0][0];
        }

        for (int i=2; i<sticker_num; i++) {
            dp[0][i] = sticker[0][i] + (dp[1][i-1] > dp[1][i-2] ? dp[1][i-1] : dp[1][i-2]);
            dp[1][i] = sticker[1][i] + (dp[0][i-1] > dp[0][i-2] ? dp[0][i-1] : dp[0][i-2]);
        }

        int result = (dp[0][sticker_num-1] > dp[1][sticker_num-1]) ? dp[0][sticker_num-1] : dp[1][sticker_num-1];
        printf("%d\n", result);

        caseCount--;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int caseCount;
    cin >> caseCount;

    while(caseCount) {
        int sticker_num;
        cin >> sticker_num;

        vector<vector<int>> sticker(2, vector<int>(sticker_num));
        for (int i=0; i<2; i++) {
            for (int j=0; j<sticker_num; j++) {
                cin >> sticker[i][j];
            }
        }

        vector<vector<int>> dp(2, vector<int>(sticker_num));
        dp[0][0] = sticker[0][0];
        dp[1][0] = sticker[1][0];

        if(sticker_num > 1) {
            dp[0][1] = sticker[0][1] + dp[1][0];
            dp[1][1] = sticker[1][1] + dp[0][0];
        }

        for(int i=2; i<sticker_num; i++) {
            dp[0][i] = sticker[0][i] + max(dp[1][i-1], dp[1][i-2]);
            dp[1][i] = sticker[1][i] + max(dp[0][i-1], dp[0][i-2]);
        }

        int result;
        if(sticker_num > 0) {
            result = max(dp[0][sticker_num-1], dp[1][sticker_num-1]);
        }
        
        cout << result << endl;

        caseCount--;
    }

    return 0;
}