문제링크:https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
작성코드
풀이
2차원 dp 문제이다.
우선 문제를 분석해보면 이전 집과의 색이 동일하면 안되는 규칙을 가지고 가장 작은 비용으로 집을 칠해야한다.
즉, 이전 집의 색과 다른 두 색 중 작은 값이 채택된다.
이게 계속 반복되는데
dp 방식으로 저장해줄 값은 해당 색을 선택했을때 이전까지 최소 도달 값 + 현재값이 된다.
이를 코드로 구현하면
이와 같이 나온다.
for문을 돌면서 dp를 bottom-up 방식으로 1번 집부터 값을 저장해준다.
for 문에서 범위를 (1,N) 으로 잡은 이유는 이전 값을 참조해야하는데 첫번째 집의 경우 이전 값이 없기 때문에 값을 그대로 dp[0][0~2]로 두기 위해서 이다.
출력 값은 집이 0번부터 시작하므로 N-1번 집이 N번째 집이 되어
print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2])) 을 출력해주면 된다.
'백준 > Python' 카테고리의 다른 글
| [백준] 9461 파도반 수열 (python 파이썬) (0) | 2022.11.27 |
|---|---|
| [백준] 11659 구간 합 구하기 (python 파이썬) (0) | 2022.11.24 |
| [백준] 1904 01타일 (python 파이썬) (0) | 2022.11.14 |
| [백준] 9184 신나는 함수 실행 (python 파이썬) (0) | 2022.11.09 |
| [백준] 24039 2021은 무엇이 특별할까? (python 파이썬) (0) | 2022.11.07 |