목록동적계획법 (1)

john8538 님의 블로그

백준-1149번 RGB거리

https://www.acmicpc.net/problem/1149  동적계획법 즉 DP를 활용하여 문제를 해결할 수 있다.  그림을 통하여 문제를 조금 더 간편하게 이해해보자.    문제 이해N개의 집이 있고, 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다.인접한 집들은 서로 다른 색으로 칠해져야 한다.각 집을 각 색으로 칠하는 비용이 주어진다.목표는 모든 규칙을 만족하면서 전체 비용을 최소화하는 것.해결 접근 방식 (동적 프로그래밍)그림에서 보이듯이, 각 단계(집)마다 3가지 선택(R, G, B)이 존재.각 단계에서의 최소 비용은 이전 단계의 결과에 의존.따라서 이를 해결하려면 전에 단계에서 가져올 수 있는 숫자중 최소를 구한 후, 현재 위치와 더하면 된다!이를 계속 한 행..
백준 & 알고리즘 2024. 8. 16. 02:52
이전 Prev 1 Next 다음