[백준 9465번 dp 알고리즘] 스티커 문제 파이썬 풀이

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

 

 

이 문제는 다이나믹프로그래밍 문제인건 다들 알고 계실 겁니다.

이 문제를 보자마자 바텀업으로 접근하면 쉽겠다라는 생각이 들었습니다.

 

 

간단하게 생각해 봤을 때 

이런 모양이 나온다고 생각할 수 있습니다.

 

하지만 생각을 조금만 더 해보면 

 

 

값에 따라 이러한 형태도 출력이 가능하다는 것 을 알 수 있습니다.

 

그럼 간단히 생각하면 각 위치에 따라 최대값을 저장해서

dp[i] 값을 저장할 때  마지막에 저장한 위치가 위쪽이라면 dp[i-1] + down(아래값) 혹은 dp[i-2] + up(위의 값)이라는 발상을 해볼 수 있습니다. 이 아이디어로 점화식을 그려 코드를 작성하면

 

 

import sys
input = sys.stdin.readline

test_case = int(input().strip())
res = []
for _ in range(test_case):
    n = int(input().strip())
    up = list(map(int, input().strip().split()))
    down = list(map(int,input().strip().split()))
  
    dp = [0] * (n+1)
    dire = [0] * (n+1)
    if up[0] > down[0]:
        dp[1] = up[0]
        dire[1] = 0
    else:
        dp[1] = down[0]
        dire[1] = 1
    
    for i in range(2,n+1):
        if dire[i-1] == 0:
            dp[i] = max(dp[i-1] + down[i-1], dp[i-2]+ up[i-1])
            if dp[i] == (dp[i-1] + down[i-1]):
                dire[i] = 1  
            else:
                dire[i] = 0
        else:
            dp[i] = max(dp[i-1] + up[i-1], dp[i-2]+ down[i-1])
            if dp[i] == (dp[i-1] + up[i-1]):
                dire[i] = 0
            else:
                dire[i] = 1
        
    res.append(dp[-1])

 

이러한 코드가 나옵니다. 하지만 이 방법은 잘못됐습니다. 다음 예시를 보시죠.

1

10

1 2 3 4 5 6 7 8 9 10

2 1 2 1 2 1 3 2 3 20

이라는 값이 입력되었을때

위의 코드대로라면 아래 결과를 출력합니다.

 

어 맞는거 아니야? 라고 생각할 수 있지만 

 

 

이렇게 되어서 최대값은 50입니다.

이때부터 머리가 아파오기 시작합니다.

아 맞는거같은데? 아 분명 실버 1문제인데 왜 안풀리지?

당연합니다. 체감상 dp문제는 실버문제여도 좀 빡세요. 기죽지말고 꾸준히 풀다보면 적응할 수 있습니다.

 

하지만 조금 더 쉽게 생각할 수 있습니다.

dp테이블을 두개 만들어서 그 때마다 값을 꺼내쓰면 됩니다.

무슨말이냐 하면

 

각 위치의 최대값이 아닌 마지막 값으로 위를 저장했을 때 가장 큰 값, 마지막 값으로 아래를 저장했을 때 가장 큰 값

을 저장합니다. 

 

첫번째 인덱스는 당연히 초기값 설정을 해줘야하고 

각 인덱스에서 최적의 값을 계산해주면 됩니다.

 

그에 맞춘 코드입니다.

import sys
input = sys.stdin.readline

test_case = int(input().strip())
res = []

for _ in range(test_case):
    n = int(input().strip())
    up = list(map(int, input().strip().split()))
    down = list(map(int, input().strip().split()))

    if n == 1:
        res.append(max(up[0], down[0]))
        continue

    dp_up = [0] * n
    dp_down = [0] * n

    dp_up[0] = up[0]
    dp_down[0] = down[0]

    dp_up[1] = max(up[1] + down[0], up[0])
    dp_down[1] = max(down[1] + up[0], down[0])

    for i in range(2, n):
        dp_up[i] = max(dp_down[i-1] + up[i], dp_down[i-2] + up[i])
        dp_down[i] = max(dp_up[i-1] + down[i], dp_up[i-2] + down[i])

    res.append(max(dp_up[-1], dp_down[-1]))

for x in res:
    print(x)

 

이 코드를 보면 

 

이러한 표를 그려 볼 수 있습니다.

따라서 반례도 통과를 했습니다.

 

바텀업 방식 설명 정리

1. 입력 처리: 입력된 테스트 케이스의 수와 각 테스트 케이스의 배열들을 읽어들입니다.
2. 초기화: 두 개의 DP 배열 dp_up과 dp_down을 초기화합니다. 이 배열들은 각각 위쪽 배열과 아래쪽 배열의 부분 합을 저장합니다.
3. 초기 값 설정: 첫 번째 인덱스의 값들은 직접 할당합니다. 두 번째 인덱스부터는 바로 이전 인덱스의 값을 사용하여 초기 값을 설정합니다.
4. DP 테이블 채우기: 각 인덱스에서 최적의 값을 계산합니다. 이 때, 바로 이전 인덱스의 값을 사용하여 현재 인덱스의 최적 값을 결정합니다.
5. 결과 저장: 각 테스트 케이스의 결과를 저장하고, 모든 테스트 케이스에 대해 결과를 출력합니다.

 

끝으로

다이나믹프로그래밍은 흔히 뉴비폭사 개념이라고도 합니다. 대부분의 자신감을 얻은 백준러들이 dp에서 좌절하죠

대부분의 사람들은 안풀리는 문제는 과감하게 여러가지 풀이를 보면서 학습한다고도 합니다.

저 또한 이 방식으로 학습하다보니 어느정도는 감이 잡히는 듯 합니다.

다들 수고하셨습니다. 

오른쪽 위에 구독버튼 있습니다. 구독하고 같이 문제 풀어봐요!