백준 1149번: RGB거리

문제

• https://www.acmicpc.net/problem/1149
• 동적 프로그래밍을 활용해 최적해 구하기

기록 포인트

• 부분 문제를 정의하는 방식
  • 한 시점에서의 선택이 뒤따르는 시점들의 선택에 영향을 미치므로, 각 시점이 처할 수 있는 상태를 고려해 부분 문제를 정의
  • 부분 문제의 개수는 '시퀀스의 길이 N' × '각 시점이 놓일 수 있는 상태(state)의 개수 S'
• '가능한 상태'와 '선택지'의 구분
  • 상태(state)는 시퀀스 상의 한 시점 i(아이템)이 처할 수 있는 상황, 즉 DAG 상의 노드
  • 선택지(choice)는 시점 i에서 시점 i+1로 넘어갈 때 취할 수 있는 행동, 즉 DAG 상의 간선
  • 각 시점마다 처할 수 있는 상황의 개수가 S개이므로, 부분 문제의 개수는 N × S
• 문제에 적용하기
  • 순서대로 놓인 N개의 집 (시퀀스)
  • 각 순서의 집이 놓일 수 있는 상태는 R,G,B로 3개
  • 각 부분 문제에서 취할 수 있는 선택지는 2개
    • n의 상태가 R일 때, n-1의 상태는 [G,B] (역으로 추적하도록 구성)
    • n의 상태가 G일 때, n-1의 상태는 [R,B]
    • n의 상태가 B일 때, n-1의 상태는 [R,G]
  • DAG 구성
    • 부분 문제의 개수는 N x 3개
    • n번째 집이 놓인 3개의 상태 중 하나(즉 n번 시점의 부분문제 중 하나)에서 어떤 선택을 취하는지에 따라 n-1번째 집이 놓일 수 있는 상태 중 하나(이전 시점의 부분문제 중 하나)로 이동
• (추가 예시) 슈퍼마리오를 DP로 플레이한다면,
  • 게임 플레이하는 각각의 시점 N개
  • 각 시점이 놓일 수 있는 상태는 '화면의 픽셀, 마리오 속도, 남은 시간 등의 조합' S개
  • 각 부분 문제에서 취할 수 있는 선택지는 '점프, 좌우 이동' C개
  • DAG 구성
    • 부분 문제의 개수는 N x S개
    • 시점 n에 놓인 S개의 상태 중 하나에서 어떤 선택을 취하는지에 따라 시점 n+1에 놓인 S개의 상태 중 하나로 이동

접근 방식

• 제출 답안 참고

제출 답안

import sys

N = int(sys.stdin.readline())
costs = []
for _ in range(N):
    cost = tuple(map(int, sys.stdin.readline().split()))
    costs.append(cost)

# 1단계: 부분 문제 정의
# - fn(seq[i:], R) = i번째 집을 R로 시작하여 뒤따르는 집들을 칠하는 최소 비용
#   = i번째 집을 R로 칠하는 비용 + (i+1)번째 집을 G 또는 B로 시작하여 뒤따르는 집들을 칠하는 최소 비용 
#   = R(i) + min( fn(seq[i+1:], G), fn(seq[i+1:], B) )
# - solve(seq[i:]) = min( fn(seq[i:],R), fn(seq[i:],G), fn(seq[i:],B) )
# - 각 집이 취할 수 있는 상태(state)의 개수는 3개이며, 전체 부분 문제의 개수 N * 3

# 2단계: 메모 테이블 생성
# - 각 부분 문제의 정답을 저장하는 메모 테이블 생성
# - 집의 위치 0 ~ N-1이고, i번째 집을 R,G,B로 시작하는 최소 비용
# - 계산 편의를 위해 인덱스가 N인 집을 추가
memo = [[0, 0, 0] for _ in range(N+1)] # 순서대로 R, G, B

# 3단계: 부분 문제의 선후관계에 따라 문제 해결
# - 모든 부분 문제를 적어도 한번씩 풀어야하므로 상향식으로 구성
# - 부분 문제 정의에 따라 맨 뒤의 집부터 해결 (topological order)
for i in range(N-1, -1, -1):
    # i번째 집이 고려할 수 있는 3가지 색 중 하나 선정
    for color in range(3):
        # 선정되지 않은 나머지 2가지 색으로 뒤따르는 집의 최소 비용 확인
        min_subscore = float("inf")
        for other in range(3):
            if color != other:
                min_subscore = min(min_subscore, memo[i+1][other]) 
        memo[i][color] = costs[i][color] + min_subscore

# 4단계: 본래의 문제 해결
# - 인덱스 0번째 집을 R, G, B 중 하나로 시작하는 비용 중 최소값 출력
min_score = min(memo[0])
print(min_score)