[BOJ] 백준 9465 스티커 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

💣 문제 이해

 

각 스티커에는 점수가 부여되어 있으며, 한 스티커를 선택하면 그 상하좌우의 스티커는 선택할 수 없다는 조건이 주어져있다.

2행 n열의 스티커 중에서 조건을 만족하며 선택했을 때, 얻을 수 있는 최대의 점수를 구하는 문제이다.

 

한 스티커를 선택함에 따라 다음 선택지가 결정될 것만 같아 그리디(Greedy algorithm) 방식일 것 같으나,

그렇게 해서는 진짜 최대값을 찾을 수가 없다.

 

모든 가능한 선택지에 대해 각각 구할 수 있는 최대값을 찾아야한다고 판단했다.

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

💭 풀이 과정

 

첫 번째 테스트 케이스의 경우이다.

 

 

<inpArr>

50	10	100	20	40
30	50	70	10	60

출발점은 50 또는 30이다.

 

50을 선택하는 경우, 우측의 10과 아래의 30을 선택할 수 없다.

그렇다면 다음으로 대각선 아래의 50, 70, 10, 60, .... 을 선택할 수 있다. (30으로 시작하는 경우는 경우 대각선 위를 체크)

 

그러나, 대각선 아래 첫 번째와 두 번째만 비교하면 된다.

대각선 아래 세 번째인 10을 보면,

50 + 10 보다 50 + 50 + 100 + 10이 훨씬 크기 때문에 제외해도 되는 것이다.

 

이런 규칙으로 dp 배열을 채우면 아래와 같다.

 

 

 

<dpArr>

50	40	200	140	250
30	100	120	210	260

 

좌측에서 우측으로 이동하면서 현재 스티커를 기준으로 얻을 수 있는 최대 점수가 기록이 된다.

이 예제에서는 260이 최대점이 된다.

 

 

 

작성 언어: C++

 

#include <cstdio>
#include <algorithm>

int main(){
    int tcNum = 0, nNum = 0, answer = 0;
    int inpArr[2][100010] = {0,};
    int dpArr[2][100010] = {0,};
    
    scanf("%d", &tcNum);
    
    for (int temp = 0; temp < tcNum; ++temp) {
        scanf("%d", &nNum);
        //######## 입력 데이터 inpArr에 받아오기 ########//
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < nNum; ++j) {
                scanf("%d", &inpArr[i][j]);
            }
        }
        
        // 맨 좌측 0열은 그대로 가져온다.
        dpArr[0][0] = inpArr[0][0];
        dpArr[1][0] = inpArr[1][0];
        // 1열은 직접 채워준다.
        // (0행은 현재와 대각선 아래를 합, 1행은 현재와 대각선 위를 합)
        dpArr[0][1] = inpArr[0][1] + inpArr[1][0];
        dpArr[1][1] = inpArr[1][1] + inpArr[0][0];
        
        for (int j = 2; j < nNum; ++j) {
            dpArr[0][j] = inpArr[0][j] + std::max(dpArr[1][j-2], dpArr[1][j-1]);
            dpArr[1][j] = inpArr[1][j] + std::max(dpArr[0][j-2], dpArr[0][j-1]);
            // 열 값을 채울 때마다, 기존 최대값보다 큰 값을 찾으면 대체한다.
            answer = answer < dpArr[0][j] ? dpArr[0][j] : answer;
            answer = answer < dpArr[1][j] ? dpArr[1][j] : answer;
        }
        
        printf("%d\n", answer);
        answer = 0;
    }
    
    return 0;
}

 

 

 

🏆 배운 점

 

처음 시도할 때, 벡터를 사용하면서 2차원 배열을 선언하려고 하다보니, 필요 이상으로 소스가 길어지는 부분들이 있었다.

STL 사용에 더 익숙해지려고 일부러 시도해봤는데, 일반 배열을 사용하는 것이 훨씬 생산적이었다.

 

생각한 풀이를 소스로 구현할 때, 어떤 자료형을 쓸 것인가도 현명하게 선택해야겠다는 생각이 들었다.