[백준] 1149번 : RGB거리 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1149번: RGB거리

 

1. 문제 설명

2. 풀이과정

해당 문제는 다음 집 색이 이전 집 색의 결과에 영향을 받으므로 이전 집 색의 결과를 다시 사용하여 해결하는 다이나믹 알고리즘 문제이다.

각 집은 3가지 색으로 칠할 수 있기 때문에 다음 집 색의 3가지 선택지 별로 이전 집의 가능한 색 결 중 최솟값을 더하여 3가지 경우를 각각 구하고 마지막 집까지 색을 선택하였으면 마지막 집의 결과에서 최솟값을 찾으면 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 집의 수를 입력받는다. N = int(sys.stdin.readline())
3. 각 집 별로 색을 칠하는 비용을 입력받아 저장할 리스트를 생성한다. RGB = list()
4. 집의 수만큼 반복하며 for _ in range(N)
5. 각 색을 칠하는 비용을 입력받아 리스트 형태로 추가한다. RGB.append(list(map(int, sys.stdin.readline().split())))
6. 제일 처음 집의 다음 집부터 시작하여 마지막 집까지 반복한다. for i in range(1, len(RGB))
7. 다음 집의 각 색의 값을 선택할 경우 이전 집이 칠할 수 있는 색 중 최솟값을 선택하여 더한 뒤, 그 값을 해당 색을 선택했을 때의 결과 값으로 저장한다. RGB[i][0] += min(RGB[i - 1][1], RGB[i - 1][2])
8. 다음 집의 색은 이전 집과 겹칠 수 없기 때문에 다음 집의 색을 선택하면 이전 집의 경우에서 해당 색을 제외하고 나머지 값 중에서 최솟값을 선택해 더한다. RGB[i][1] += min(RGB[i - 1][0], RGB[i - 1][2])
9. RGB[i][2] += min(RGB[i - 1][0], RGB[i - 1][1])
10. 마지막 집까지 색을 선택하면 마지막 집의 각 색 중 최솟값을 출력한다. print(min(RGB[-1]))

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

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

for i in range(1, len(RGB)):
    RGB[i][0] += min(RGB[i - 1][1], RGB[i - 1][2])
    RGB[i][1] += min(RGB[i - 1][0], RGB[i - 1][2])
    RGB[i][2] += min(RGB[i - 1][0], RGB[i - 1][1])

print(min(RGB[-1]))