백준(baekjoon) 1149번: RGB 거리(실버 1, 파이썬 PYTHON) - 동적 계획법 1

문제

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

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

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

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

1149번: RGB거리

 

import sys

N=int(sys.stdin.readline())
house=[]
house.append([0,0,0])

for _ in range(N):
  RGB_cost=list(map(int,sys.stdin.readline().split()))
  house.append(RGB_cost)

for x in range(1,N+1):
  house[x][0]=min(house[x-1][1]+house[x][0],house[x-1][2]+house[x][0])
  house[x][1]=min(house[x-1][0]+house[x][1],house[x-1][2]+house[x][1])
  house[x][2]=min(house[x-1][0]+house[x][2],house[x-1][1]+house[x][2])

print(min(house[N]))

 

※ 동적 계획법 1

 

 

● 먼저 N을 입력받은 후, 배열 [0,0,0] 이 들어있는 house 배열을 정의해준다. 그 뒤로 들어오는 입력값들을 배열로 만들어서 각 배열을 house 에 차례대로 append 해준다. house 배열 안에 들어있는 i번째 배열은 i번 집을 각각 빨강, 초록, 파랑으로 칠할 때 드는 비용을 나타낸다.

 

● x는 1부터 N 까지의 값을 가진다. 

 

● house[x][0] 에는 x번 집을 빨강으로 칠할 수 있는 경우 중 비용이 가장 작은 값이 들어가게 된다.

-> case 1: x-1 번 집을 초록으로 칠하는 경우 중 가장 작은 값과 x번 집을 빨강으로 칠하는 값 

-> case 2: x-1 번 집을 파랑으로 칠하는 경우 중 가장 작은 값과 x번 집을 빨강으로 칠하는 값

이 두 값 중 더 작은 값을 house[x][0] 에 넣어준다.

 

● house[x][1] 에는 x번 집을 초록으로 칠할 수 있는 경우 중 비용이 가장 작은 값이 들어가게 된다.

-> case 1: x-1 번 집을 빨강으로 칠하는 경우 중 가장 작은 값과 x번 집을 초록으로 칠하는 값 

-> case 2: x-1 번 집을 파랑으로 칠하는 경우 중 가장 작은 값과 x번 집을 초록으로 칠하는 값

이 두 값 중 더 작은 값을 house[x][1] 에 넣어준다.

 

● house[x][2] 에는 x번 집을 파랑으로 칠할 수 있는 경우 중 비용이 가장 작은 값이 들어가게 된다.

-> case 1: x-1 번 집을 빨강으로 칠하는 경우 중 가장 작은 값과 x번 집을 파랑으로 칠하는 값 

-> case 2: x-1 번 집을 초록으로 칠하는 경우 중 가장 작은 값과 x번 집을 파랑으로 칠하는 값

이 두 값 중 더 작은 값을 house[x][2] 에 넣어준다.

 

● N번째 집까지 모두 칠한 비용의 최소값은 house[N][0], house[N][1], house[N][2] 의 값 중 최소값을 출력해주면 답이 나온다!!

 

 

결과