[백준 1149 파이썬/python] RGB거리

RGB거리

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	96017	51936	38677	53.374%

문제

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보다 작거나 같은 자연수이다.

출력

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

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

96

풀이

n = int(input())
a = [(0,0,0)] + [tuple(map(int,input().split())) for _ in range(n)]
d = [[0,0,0] for _ in range(n+1)]
for i in range(1, n+1):
    d[i][0] = min(d[i-1][1], d[i-1][2]) + a[i][0]
    d[i][1] = min(d[i-1][0], d[i-1][2]) + a[i][1]
    d[i][2] = min(d[i-1][0], d[i-1][1]) + a[i][2]
print(min(d[n][0], d[n][1], d[n][2]))

1. n = int(input()) : 입력으로 첫 번째 줄에 집의 개수 n을 받습니다.

2. a = [(0,0,0)] + [tuple(map(int,input().split())) for _ in range(n)] : 각 집을 칠하는 비용을 입력받아 리스트 a에 저장합니다. a의 첫 번째 요소는 더미 값(0,0,0)입니다.

3. d = [[0,0,0] for _ in range(n+1)] : n+1 크기의 d (동적 프로그래밍 테이블)를 생성하고 모든 요소를 (0,0,0)으로 초기화합니다.

4. for i in range(1, n+1) : 1부터 n까지 반복합니다.
   • d[i][0] = min(d[i-1][1], d[i-1][2]) + a[i][0] : 빨강색으로 칠할 경우, 이전 집의 초록색 또는 파랑색 비용 중 작은 값을 선택하고 현재 집의 빨강색 비용을 더합니다.
   • d[i][1] = min(d[i-1][0], d[i-1][2]) + a[i][1] : 초록색으로 칠할 경우, 이전 집의 빨강색 또는 파랑색 비용 중 작은 값을 선택하고 현재 집의 초록색 비용을 더합니다.
   • d[i][2] = min(d[i-1][0], d[i-1][1]) + a[i][2] : 파랑색으로 칠할 경우, 이전 집의 빨강색 또는 초록색 비용 중 작은 값을 선택하고 현재 집의 파랑색 비용을 더합니다.

5. print(min(d[n][0], d[n][1], d[n][2])) : 마지막 집에서 각 색으로 칠하는 비용 중 최소값을 출력합니다.

Uploaded by N2T