반응형
문제풀이
1. dp의 각 요소의 의미는 다음과 같다.
dp[0] : 입력 받은 칸을 red로 칠했을 때 코스트의 최솟값
dp[1] : 입력 받은 칸을 green로 칠했을 때 코스트의 최솟값
dp[2] : 입력 받은 칸을 blue로 칠했을 때 코스트의 최솟값2. 현재 칸의 페인트의 코스트 r,g,b를 입력받았다면, 위의 관계를 아래와 같이 쓸 수 있다.
dp[0] = min(dp[1],dp[2])+r
dp[1] = min(dp[0],dp[2])+g
dp[2] = min(dp[0],dp[1])+bPython Code
|
1
2
3
4
5
6
7
8
9
10
11
12
|
import sys
readline = sys.stdin.readline
def main(n):
dp = list(map(int,readline().split()))
for _ in range(n-1):
r,g,b = map(int,readline().split())
dp = [min(dp[1],dp[2])+r, min(dp[0],dp[2])+g,min(dp[0],dp[1])+b]
print(min(dp))
if __name__ == '__main__':
n =int(readline())
main(n)
|
cs |
문제 링크
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 4344 평균은 넘겠지 Python (0) | 2020.12.09 |
|---|---|
| 백준 20162 간식 파티 Python (0) | 2020.12.08 |
| 백준 1309 동물원 (0) | 2020.12.07 |
| 백준 20299 3대 측정 (0) | 2020.12.04 |
| 백준 11057 오르막 수 Python (0) | 2020.12.03 |