[백준✨] 12849번 <본대 산책> / Python 문제풀이 /

해답)

import sys
sys.setrecursionlimit(10**8)

def input():
  return sys.stdin.readline().rstrip()

'''
@@@@ 입력받기 @@@@
'''

N = int(input())
board = []
dp = [[[-1 for _ in range(3)] for _ in range(3)] for _ in range(N)] # 메모이제이션

for _ in range(N):
  board.append(list(map(int, input().split())))

'''
@@@ 함수들 @@@
'''
def getMin(prevs, color_list): # 고를 수 있는 것 중 최솟값 고르기
  res = float('inf')
  for i in range(3):
    if i in prevs:
      continue
    res = min(res, color_list[i])
  # print("res ==> ", res)
  return res

def dfs(start, now, prev): 
  if now == N-1:
    return getMin([start,prev], board[now])
  if dp[now][prev][start] != -1:
    return dp[now][prev][start] 
  res = float('inf')
  for i in range(3):
    if i == prev:
      continue
    val = board[now][i]
    res = min(res, val + dfs(start, now+1, i))
    # print(f"res = min(res, {val} + dfs(start, now+1, i)), res= {res}")
  dp[now][prev][start] = res
  return res

def loop(): # 시작을 달리하며 dfs 실행
  res = float('inf')
  for i in range(3):
    res = min(res, board[0][i]+dfs(i, 1, i))
  return res

print(loop())

---

풀이)

RGB 거리 1 과 는 다르게,

첫번 째 고른 집은, 마지막에 고른 집과 같으면 안된다!!

 

탐색하는 dfs 함수를 만들어주고, 첫 번째를 각기 다르게 해주기 위해 dfs를 실행시켜주는 함수인 loop 함수를 만들었다.

작동방식은 dp 배열에 메모이제이션 해주면서, 루프를 돌면서 기록하는 것이다.

dp는 dp[현재집index][이전집color][처음고른집color] 형태로 만들어 주었다.

 

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.