[백준9465&파이썬] DP를 풀때는 N이 1일때부터 하나씩 늘려가며 경우의 수를 따져보자.

# 문제

9465번: 스티커

# 코드

import sys

def solve() :
  n = int(sys.stdin.readline().strip())
  stickers = list()
  for row in range(2):
    line = list(map(int, sys.stdin.readline().split()))
    stickers.append(line)

  # 현재 시점에서 대각선으로 한칸전과 두칸전 중 max값이 그 스티커의 최대값
  for i in range(1,n) :
    if i == 1 : # 1일때는 특이 케이스가 된다. 두칸 뒤를 볼 수가 없다.
      stickers[0][i] += stickers[1][i-1]
      stickers[1][i] += stickers[0][i-1]
      continue
    stickers[0][i] = max(stickers[1][i-1],stickers[1][i-2]) + stickers[0][i]
    stickers[1][i] = max(stickers[0][i-1],stickers[0][i-2]) + stickers[1][i]

  # print(stickers)
  print(max(stickers[0][n-1],stickers[1][n-1]))



T = int(sys.stdin.readline().strip())
for _ in range(T):
  solve()

 

## 실패한 풀이

# --- 그리디를 이용했던 풀이는 역시나 틀렸다 --- #
DIRS = [
  (-1, 0), (0, 1), (1, 0), (0, -1)
  ]

def solve():
  n = int(sys.stdin.readline().strip())
  stickers = list()
  max_heap = list()
  visit = [[False] * n for _ in range(2)]
  for row in range(2):
    line = list(map(int, sys.stdin.readline().split()))
    stickers.append(line)
    for col, cost in enumerate(line):
      node = (cost * -1, row, col)  # cost, row, col # -1을 곱해줌으로써 max_heap의 형태로 만든다.
      heappush(max_heap, node)
  result = 0

  visit_cnt = 0
  while len(max_heap) != 0:
    cost, row, col = heappop(max_heap)  # ( cost, row, col )
    cost *= -1  # cost에 -1을 곱해서 원복을 해야한다
    if visit[row][col] == False:  # 사용했던 곳이 아니면
      visit[row][col] = True  # 방문처리
      visit_cnt += 1
      result += stickers[row][col]
      # print(row, col)

      for dir in DIRS:  # 4방향 방문처리
        next_row = row + dir[0];
        next_col = col + dir[1]
        if 0 <= next_row <= 1 and 0 <= next_col < n and visit[next_row][next_col] == False:  # 범위 안이라면
          visit[next_row][next_col] = True  # 방문처리를 완료한다.
          visit_cnt += 1

    if visit_cnt == 2 * n:  # 모든 곳 방문했기에 종료
      # print(f"visit : {visit}")
      # print(f"visit_cnt : {visit_cnt}")
      # print(f"2*n : {2 * n}")
      break
  print(result)

# 풀이

• 크루스칼의 최대간선을 선택하는 그리디의 원리처럼 가장 값이 큰 우표를 선택해나가고 4방향에 대한 방문처리를 하도록했다. 또한 반복문으로 매번 찾는게 아닌, 큐에 최대값과 좌표를 넣어두고 뽑아 사용할 수 있도록 했다. 당연히 실패한 풀이이다.
  • 그리디는 선택한 값이 최적의 값이며 이후의 선택에 영향을 미치지 않아야한다. 그러나 우표는 4방향에 대해서 끊어지기 때문에 어떠한 우표를 선택했냐에 따라서 이후의 값에 영향을 끼치기 때문이다
• DP를 사용해야함을 짐작했다. 먼저 DP에서는 가장먼저 선택하여 확정짓는 값에 대한 명확한 근거가 존재해야한다. 그 근거를 찾았다면 점화식을 세우고 간단하게 코딩이 가능하다. 
• N이 1일때부터 차근차근 4일때까지 만들어 보았다. 그리고 선택 될 수 있는 경우의 수가 두가지씩 총 4가지 존재 함을 알았다.

• N이 3일때 주목해보자, 50(0행0열)에 대해서 자신의 대각선(1행1열)과 대각선에서 한칸 앞(1행2열)이 선택 가능함을 볼 수 있다.
• 30(1행0열)도 똑같다, 초록색 선으로 이어진 10(0행1열)과 100(0행2열)이 선택가능함을 알 수 있다.
  • 여기서 70(1행2열)을 선택하는 경우도 있지 않냐고 의문을 가질 수 있다.
  • 70(1행2열)을 선택하는 경우는 10(0행1열)을 선택했을때 일어날 수 있는 경우의 수의 포함된다. 그렇기 때문에 지금 구해지는 것이 아닌 이 이후에 알아서 구해지게 된다.
• 해결 전략을 위해서는 관점에 변화가 필요하다. 앞에서 뒤 ( 0열에서 1열.. 2열)을 보는 것이 아닌 뒤에서 앞을 봐야한다. (2열에서 0열과 1열을) 그렇게 되면, 앞에서 선택했던 값이 최대값임을 보장할 수 있고 이를 토대로 현재의 값을 확정 지을 수 있다.