728x90
solved.ac의 Class 4 문제 중 RGB거리 문제이다.
문제 조건
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.
각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서
모든 집을 칠하는 비용의 최솟값을 구하는 문제이다.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1) 번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
이전 집의 색과 현재 집의 색은 같으면 안 되므로 R, G, B로 경우를 나누어 계산해야 한다.
즉, 현재 집과 같은 색을 제외한 값들의 최솟값과 현재 자신의 값을 더하면 된다.
해결했던 코드는 다음과 같다.
import sys
if __name__ == '__main__':
n = int(sys.stdin.readline())
lst = []
dp = [[0 for _ in range(3)] for _ in range(n)]
for i in range(n):
lst.append(list(map(int, sys.stdin.readline().split())))
dp[0] = lst[0] # dp의 첫 줄을 맨 처음 집으로 세팅
for i in range(n):
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + lst[i][0] # 이전 집의 최솟값 + dp[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + lst[i][1] # 이전 집의 최솟값 + dp[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + lst[i][2] # 이전 집의 최솟값 + dp[i][2]
print(min(dp[n-1])) # 결과 출력
참고했던 블로그: https://velog.io/@hope1213/%EB%B0%B1%EC%A4%80-1149-RGB%EA%B1%B0%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC
728x90
'Algorithm > BOJ' 카테고리의 다른 글
[백준] 1629번 Silver 1 곱셈, Java 코드 (0) | 2024.10.06 |
---|---|
[백준] 16953번 - Silver 2 A -> B, 파이썬 코드 (0) | 2024.09.28 |
[백준] 15663번 - Silver 3 N과 M (9), 파이썬 코드 (0) | 2024.09.11 |
[백준] 15654번 - Silver3 N과 M(5), 파이썬 코드 (0) | 2024.09.07 |
[백준] 15650번 - Silver 3 N과 M (2), 파이썬 코드 (0) | 2024.09.06 |