문제 링크
https://www.acmicpc.net/problem/1149
- 문제 설명
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 (추가 시간 없음) 128 MB 125760 72051 53403 56.312% 문제
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예제 입력 2 복사
3 1 100 100 100 1 100 100 100 1예제 출력 2 복사
3예제 입력 3 복사
3 1 100 100 100 100 100 1 100 100예제 출력 3 복사
102예제 입력 4 복사
6 30 19 5 64 77 64 15 19 97 4 71 57 90 86 84 93 32 91예제 출력 4 복사
208예제 입력 5 복사
8 71 39 44 32 83 55 51 37 63 89 29 100 83 58 11 65 13 15 47 25 29 60 66 19예제 출력 5 복사
253출처
-
문제를 번역한 사람: baekjoon
-
빠진 조건을 찾은 사람: djm03178
-
문제의 오타를 찾은 사람: fail456
-
데이터를 추가한 사람: rdd6584
알고리즘 분류
-
N = int(input())
RGB = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0][0], dp[0][1], dp[0][2] = RGB[0] # 첫 번째 집의 비용은 입력 값 그대로 사용
for i in range(1, N): # 두 번째 집부터 마지막 집까지 반복하며 최소 비용 계산
# 현재 집을 빨강으로 칠했을 때의 최소 비용 계산
dp[i][0] = RGB[i][0] + min(dp[i-1][1], dp[i-1][2])
# 현재 집을 초록으로 칠했을 때의 최소 비용 계산
dp[i][1] = RGB[i][1] + min(dp[i-1][0], dp[i-1][2])
# 현재 집을 파랑으로 칠했을 때의 최소 비용 계산
dp[i][2] = RGB[i][2] + min(dp[i-1][0], dp[i-1][1])
print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]))
dp문제는 역시 아직 서투르다
생각하는데 오래걸렸다.
숏폼 미디어에 노출되어 뇌기능에 저하된것같다
재활의 필요성을 느낌…
