백준 9465 : 스티커 (파이썬)

DP 문제이다.

DP 문제는 반복의 맨 처음 단계에서 어떤 패턴을 찾으면 그 다음은 빠르게 풀린다.

그리고 항상 그걸 못 찾아서 문제다...

 

다만 확실히 DP 문제를 풀면 풀수록 뇌가 DP 화 되는 느낌이 있다.

나 같은 범재도 이런식으로 반복하면 그래도 요령이 생기는구나 싶어서 보람은 있었다.

 

※ 결국 노력과 반복이 답이다...

 

• 문제 풀이 아이디어 공유 :
  1. 줄 == 가로방향, 칸 == 세로방향
  2. 먼저 각 줄의 i 번째까지 누적합을 저장해 줄 dp 리스트를 만든다.
     • 0 으로 마진을 두는게 편해서 인덱스 번호는 항상 1 부터 시작하게 만드는 편이다. 다른 사람들은 그렇게 안 한 사람도 있었다.
     • 누적합의 패턴이 어떤지는 모르지만 여타 DP 문제가 그래왔듯 이번에도 비슷하겠거니 싶어서 일단 그렇게 만들었다.
  3. 2차원 리스트 'sticker' 를 만든다.
  4. 처음에는 중첩 for 문을 써야 하나 싶었는데 생각해 보니 스티커는 두 줄로 고정이니까 굳이 그럴 필요 없다는 것을 알았다.
  5. 스티커 윗줄과 아랫줄에서 각각 맨 처음 스티커만 놓여있다고 가정했을 때, 자기 줄에서 가장 최댓값은 자기 자신이므로 최댓값을 저장해주는 dp 에 아래와 같이 넣어준다.
     • dp[1][1] = sticker[0][0]
     • dp[2][1] = sticker[1][0]
  6. 그 다음 스티커까지 포함한다고 했을 때(2x2 크기 혹은 그 이상일 때), dp 의 각 단계에서 가장 크게 될 수 있는 값을 넣어줘야 되는데, 윗줄 아랫줄의 각 현재 자리에서 될 수 있는 제일 큰 값은 아래 둘 중 하나이다.
     • 지금 들어온 수를 포함하여 계산하는 경우 >>> 지금 들어온 수와 대각선 뒷 방향의 누적합을 더한 값
     • 지금 들어온 수를 포함하지 않고 계산하는 경우 >>> 지금 들어온 수는 무시하고 같은 줄의 내 바로 뒤의 값만 넣기
     • 두 경우를 비교하면서 큰 값을 현재 자리에 넣는다.
  7. 맨 마지막까지 위의 계산을 반복한 다음 각 줄의 가장 마지막 칸에 있는 값을 대소비교 하여 출력해준다.

 

아래는 전체 코드이다.

 

import sys
T = int(sys.stdin.readline())
for testcase in range(T):
    N = int(sys.stdin.readline())
    sticker = []
    dp = [[0] * (N + 1) for _ in range(3)]
    for _ in range(2):
        sticker.append([*map(int, sys.stdin.readline().split())])
    for i in range(1, N + 1):
        if i == 1:
            dp[1][i], dp[2][i] = sticker[0][0], sticker[1][0]
        else:
            dp[1][i] = max(dp[2][i - 1] + sticker[0][i - 1], dp[1][i - 1])
            dp[2][i] = max(dp[1][i - 1] + sticker[1][i - 1], dp[2][i - 1])
    # print(dp[-1][-1]) >>> 첫 시도 때 이렇게 해서 '틀렸습니다' 가 나왔다.
    print(max(dp[1][-1], dp[2][-1]))

 

DP 문제는 왜이렇게 다 어려운건지 모르겠다...