[백준 1149번] RGB거리 (Python 파이썬) 풀이 방법

백준 1149번 <RGB거리> 문제 보기

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

1149번: RGB거리

 

 

백준 1149번 <RGB거리> 문제 풀이

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를 떠올릴 수도 있을 것 같다.
  • 문제에 조건이 3개로 써져 있지만 사실상 조건은 하나다. 이전 집과 색이 다르면 된다. 이전 값에서 최솟값을 더해주며 최종값을 구할 수 있다.

 

• 코드 설명
  • 예제를 dp 배열에 받고 바로 계산을 해주었다. 이전 집과 색이 같을 수 없으므로 현재 위치의 색과 다른 두 가지 색 중 최솟값을 현재 위치의 값에 더해주며 정답을 만들어 나간다. 최종 집에서의 최솟값이 정답이 된다.
    
    

 

• 후기
  • 처음에는 문제가 잘 이해가 안 됐었는데 꼼꼼히 다시 읽어보니 풀이 가닥이 잡혔다. 결국에는 조건이 하나였고 DP 문제 치고는 쉬운 측에 속하는 것 같다.