[백준 1149번] RGB거리

by

백준 #1149 참조 문제

https://www.acmicpc.net/problem/1149

#1149: RGB 간격

'추천 관련글,

주택 수 N(2 ≤ N ≤ 1,000)은 첫 번째 줄에 표시됩니다. 두 번째 행부터 N행까지 첫 번째 집부터 시작하여 각 행에 빨강, 녹색, 파랑을 칠하는 비용이 나열됩니다. 집을 칠하는 비용은 1,000 미만이거나

www.acmicpc.net

백1149년 6월 문제 설명

n = int(input())
dp = (list(map(int, input().split())) for _ in range(n))

for i in range(1, n):
  dp(i)(0) += min(dp(i-1)(1), dp(i-1)(2))
  dp(i)(1) += min(dp(i-1)(0), dp(i-1)(2))
  dp(i)(2) += min(dp(i-1)(0), dp(i-1)(1))

print(min(dp(-1)(0), dp(-1)(1), dp(-1)(2)))

  • 접근하다
    • 내가 선택한 문제라서 DP 문제인 줄 이미 알고 있었다. 아무런 정보 없이 이 문제를 접하게 된다면 “최소 비용”을 찾는 데 필요한 것으로 DFS와 BFS를 생각할 수 있습니다.
    • 문제에는 세 가지 조건이 적혀 있지만 사실 조건은 하나뿐입니다. 단지 이전 집과 다른 색이어야 합니다. 최종 값은 이전 값에 최소값을 더하여 얻을 수 있습니다.

  • 코드 설명
    • 나는 dp 배열에서 예제를 얻었고 바로 계산했습니다. 색상은 이전 집과 같을 수 없으므로 현재 위치의 값에 현재 위치의 색상과 다른 두 색상의 최소값을 더하여 정답을 제공합니다. 마지막 집의 최소값이 정답입니다.

      [백준 1149번] RGB거리 1

  • 검토
    • 처음에는 문제를 잘 이해하지 못했는데 꼼꼼히 다시 읽어보니 풀이가 잘 잡혔습니다. 결국 조건은 딱 하나였고, DP 문제는 쉬운 편인 것 같다.