728x90
링크
https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
난이도(solved.ac 참고)
실버1
풀이
다이나믹 프로그래밍 문제다. DP 배열을 선언하고 첫 값은 input값으로 받은 street의 첫 열을 그대로 갖다 붙인다.
다음 열로 넘어갈 때 각 dp의 값은, 이전 열의 같은 행 값이 아닌 다른 행의 값들에 + 현재 위치한 인덱스의 street값을 더해준 것 중 더 작은 것을 넣어준다. 이 과정을 반복하고 가장 마지막 열의 가장 작은 값을 출력하면 된다.
'CS > 알고리즘' 카테고리의 다른 글
| [Python] BOJ(백준) 2960번 - 에라토스테네스의 체 (0) | 2021.10.26 |
|---|---|
| [Python] BOJ(백준) 20551번 - Sort 마스터 배지훈의 후계자 (0) | 2021.10.11 |
| [Python] BOJ(백준) 2166번 - 다각형의 면적 (0) | 2021.10.09 |
| [Python] BOJ(백준) 1092번 - 배 (0) | 2021.10.06 |
| [Python] BOJ(백준) 2170번 - 선 긋기(+ list와 tuple의 차이) (0) | 2021.10.02 |
