1 분 소요

백준 1149번 RGB거리 문제 풀이를 해보겠습니다.

출처 : 백준

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

  • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

풀이

문제 설명: i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다.

이 문제는 i번째 집을 칠하는 색을 선택할때, i-1번째 집을 칠하는 색의 비용과 i번째 집을 칠하는 비용을 모두 고려해야한다.

마지막 집의 색이 무엇이냐에 따라 1~N-1의 집 색이 결정된다.

우선 색과 가격을 저장할 2차원 리스트를 생성해 가격을 입력받고, 3가지 색을 칠하는 경우를 모두 구해 가격을 저장하고 최종 최소비용을 출력하겠다.

코드

import sys
input = sys.stdin.readline

def main():
    N = int(input()) #N의 값을 받는다
    cost = [list(map(int, input().split())) for _ in range(N)] 
    #N*3의 2차원 리스트 생성하며 N개의 집의 색칠비용을 입력받는다

    dp = [[0] * 3 for _ in range(N)] #N*3의 2차원 리스트 생성
    dp[0][0] = cost[0][0] # 첫번째 집을 빨강으로 칠할때의 가격
    dp[0][1] = cost[0][1] # 첫번째 집을 초록으로 칠할때의 가격
    dp[0][2] = cost[0][2] # 첫번째 집을 파랑로 칠할때의 가격
    
    # DP 점화식을 통해 dp 배열을 채워 나감
    # i가 x색일때의 가격과 i-1이 y,z일떄의 최소가격을 더해 dp[i][x]에 더함 (x,y,z = 색)
    for i in range(1, N): # 1부터 N-1까지
        dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])  # 빨강
        dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])  # 초록
        dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])  # 파랑
    
    # 마지막 집이 무슨 색이냐에 따라 가격이 달라짐, 최소비용을 result에 저장
    result = min(dp[N-1][0], dp[N-1][1], dp[N-1][2])
    print(result) #출력

main()

댓글남기기

참고