RGB 거리

bookmark

문제

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

출력

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

나의풀이

n = int(input())

rgb = [[0] * 4 for _ in range(n + 1)]
dp = [[0] * 4 for _ in range(n + 1)]

for i in range(n):
    rgb[i][1], rgb[i][2], rgb[i][3] = map(int, input().split())
    min_value = min(rgb[i][1], rgb[i][2], rgb[i][3])
    idx = rgb[i].index(min_value)
    if i == 0:
        dp[i][idx] = min_value
    elif dp[i - 1][idx] == 0:
        dp[i][idx] = min_value
    elif dp[i - 1][idx] != 0:
        if idx == 1:
            min_value = min(rgb[i][idx + 2], rgb[i][idx + 1])
            new_index = rgb[i].index(min_value)
            dp[i][new_index] = min_value
        elif idx == 2:
            min_value = min(rgb[i][idx - 1], rgb[i][idx + 1])
            new_index = rgb[i].index(min_value)
            dp[i][new_index] = min_value
        elif idx == 3:
            min_value = min(rgb[i][idx - 1], rgb[i][idx - 2])
            new_index = rgb[i].index(min_value)
            dp[i][new_index] = min_value

sum = sum(sum(row) for row in dp)
print(sum)
# dp 전꺼랑 다르면서 최소값

초반 예시는 맞는데 뒤의 반례들이 틀림

모범답안

n = int(input())
costs = []

# 집의 비용 정보 입력받기
for _ in range(n):
    costs.append(list(map(int, input().split())))

# dp 테이블 초기화
dp = [[0] * 3 for _ in range(n)]
dp[0] = costs[0]  # 첫 번째 집의 비용은 그대로 초기화

# 동적 계획법을 사용하여 최소 비용 계산
for i in range(1, n):
    dp[i][0] = costs[i][0] + min(dp[i - 1][1], dp[i - 1][2])  # 현재 집을 빨강으로 칠할 경우
    dp[i][1] = costs[i][1] + min(dp[i - 1][0], dp[i - 1][2])  # 현재 집을 초록으로 칠할 경우
    dp[i][2] = costs[i][2] + min(dp[i - 1][0], dp[i - 1][1])  # 현재 집을 파랑으로 칠할 경우

# 최종적으로 마지막 집까지 칠하는데 드는 최소 비용
answer = min(dp[n - 1])

print(answer)

dp에 넣을 값과 cost에 넣을 값을 따로 따로 계산

현재 집을 빨강으로 칠하는경우 전에 집은 초록 파랑이여야 하니깐

min(dp[i - 1][1], dp[i - 1][2]) 이렇게 넣어주기