문제
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
알고리즘
- 반복문을 통해 각 집의 색을 칠할 수 있는 최소 비용에 경우의 수를 구한다.
- 이후 집에 빨간색을 칠할 경우 이전 집에 초록색과 파란색 중 비용이 작은 색을 칠한다.
- 이후 집에 초록색을 칠할 경우 이전 집에 빨간색과 파란색 중 비용이 작은 색을 칠한다.
- 이후 집에 파란색을 칠할 경우 이전 집에 초록색과 빨간색 중 비용이 작은 색을 칠한다.
- 마지막 집까지 색칠한 후 비용의 최솟값을 출력한다.
코드
import sys
n = int(sys.stdin.readline())
rgb = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# 반복문을 통해 각 집의 색을 칠할 수 있는 최소 비용에 경우의 수를 구한다.
for i in range(n - 1):
rgb[i + 1][0] = min(rgb[i][1], rgb[i][2]) + rgb[i + 1][0] # 이후 집에 빨간색을 칠한 경우
rgb[i + 1][1] = min(rgb[i][0], rgb[i][2]) + rgb[i + 1][1] # 이후 집에 초록색을 칠한 경우
rgb[i + 1][2] = min(rgb[i][0], rgb[i][1]) + rgb[i + 1][2] # 이후 집에 파란색을 칠한 경우
# 마지막 집까지 색칠한 후 비용의 최솟값을 출력
print(min(rgb[n - 1]))github
GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법
내가 푼 코딩 테스트 문제와 해결법. Contribute to junjange/CodingTest development by creating an account on GitHub.
github.com
'CodingTest > Baekjoon' 카테고리의 다른 글
| [baekjoon] 백준 11727번(파이썬): 2×n 타일링 2 (0) | 2021.11.29 |
|---|---|
| [baekjoon] 백준 2193번(파이썬): 이친수 (0) | 2021.11.28 |
| [baekjoon] 백준 2156번(파이썬): 포도주 시식 (0) | 2021.11.26 |
| [baekjoon] 백준 1912번(파이썬): 연속합 (0) | 2021.11.25 |
| [baekjoon] 백준 1932번(파이썬): 정수 삼각형 (0) | 2021.11.24 |