1149. RGB거리

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

이해

• 완전 탐색을 통해 해결할 수 있지만, 완전 탐색시 O(3000^3)으로 시간 초과
• 동적 계획법을 통해 빨강, 초록, 파랑으로 칠하는 경우 중 비용이 가장 작은 경우만 저장하는 배열을 통해 해결

구현

• 빨강, 초록, 파랑으로 칠할 경우 드는 비용을 저장할 dp배열 생성
  • N개의 집을 칠하기에 빨강, 초록, 파랑 각각 칠해온 비용을 저장할 N*3배열 생성
  • dp 배열은 최대의 경우를 가정했을 때 나오는 수보다 1큰 수로 저장

dp = [[1000 * 1000+1] * 3 for _ in range(N)]

• dp배열의 첫번째 줄은 첫 집을 빨강, 초록, 파랑을 칠할 경우의 비용으로 채움

for i in range(3):
        dp[0][i] = costs[0][i]

• 1부터 N-1까지 순회하며 빨강, 초록, 파랑을 칠할 경우 최소한의 비용을 저장하며 반복

for i in range(1, N):
		# R일때
        # 올수 있는 경로 G->R, B->R
        # 현재 자기 값과 비교하여 최솟값 찾기
        dp[i][0] = min(dp[i][0], dp[i-1][1]+costs[i][0], dp[i-1][2]+costs[i][0])
        # G일때
        # 올수 있는 경로 R->G, B->G
        # 현재 자기 값과 비교하여 최솟값 찾기
        dp[i][1] = min(dp[i][1], dp[i-1][0]+costs[i][1], dp[i-1][2]+costs[i][1])
        # B일때
        # 올수 있는 경로 R->B, G->B
        # 현재 자기 값과 비교하여 최솟값 찾기
        dp[i][2] = min(dp[i][2], dp[i-1][0]+costs[i][2], dp[i-1][1]+costs[i][2])

• dp 배열 마지막에 빨강, 초록, 파랑 각각 칠해온 최소 비용 중 최소를 출력

코드

전체 코드

# 1149 RGB거리
import sys
input = sys.stdin.readline


def solution(N:int, costs:list) -> int:
	# R, G, B로 오는 방향 dp배열 생성
    dp = [[1000 * 1000+1] * 3 for _ in range(N)]
    # 초기값 설정 
    for i in range(3):
        dp[0][i] = costs[0][i]
    # dp 배열 채우기
    for i in range(1, N):
		# R일때
        # 올수 있는 경로 G->R, B->R
        # 현재 자기 값과 비교하여 최솟값 찾기
        dp[i][0] = min(dp[i][0], dp[i-1][1]+costs[i][0], dp[i-1][2]+costs[i][0])
        # G일때
        # 올수 있는 경로 R->G, B->G
        # 현재 자기 값과 비교하여 최솟값 찾기
        dp[i][1] = min(dp[i][1], dp[i-1][0]+costs[i][1], dp[i-1][2]+costs[i][1])
        # B일때
        # 올수 있는 경로 R->B, G->B
        # 현재 자기 값과 비교하여 최솟값 찾기
        dp[i][2] = min(dp[i][2], dp[i-1][0]+costs[i][2], dp[i-1][1]+costs[i][2])
    return min(dp[-1])


if __name__ == "__main__":
    N = int(input())
    costs = [list(map(int, input().split())) for _ in range(N)]
    print(solution(N, costs))