문제링크:https://www.acmicpc.net/problem/1149
작성코드
풀이
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 |