[python] 백준 1149 - RGB거리

출처 : 백준, https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

내가 푼 게 아니다.....

 

 

풀이

 

if __name__ == '__main__':
  n = int(input())
  arr = []
  for _ in range(n):
    arr.append(list(map(int, input().split())))

  pre_index = arr[0].index(max(arr[0]))

  for i in range(1, n):
    index_arr = set([0, 1, 2])
    index_arr.remove(pre_index)

    can1 = index_arr.pop()
    can2 = index_arr.pop()

    for j in range(3):
      if can1 == j:
        arr[i][j] += arr[i-1][can2]
      elif can2 == j:
        arr[i][j] += arr[i-1][can1]
      else:
        arr[i][j] += min(arr[i-1][can1], arr[i-1][can2])
        
    pre_index = arr[i].index(max(arr[i]))

  print(min(arr[n-1]))

 

로직은 다음과 같다.

 

1. 셋 중에 가장 작은 것을 배제한다.

 

26	40	83
49	60	57
13	89	99

 

2. 남은 2개 중 더할 수 있는 것끼리 더한다.

앞서 제외된 열은 남은 열 중 작은 값과 더한다.

 

26	40	83
49 + 40	60 + 26	57 + min(26, 40)
13	89	99

 

3. 남은 행에 대해 반복한다.

 

26	40	83
89	86	83
13 + min(83, 86)	89 + 83	99 + 86

 

4. 끝난 후 마지막 행 중 최솟값을 뽑는다.

 

26	40	83
89	86	83
96	172	185

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

DP 문제는 점화식을 도출하는 문제인데, 너무 식으로만 도출하려해서 그런지 아이디어가 떠오르지 않았고,

동기와 문제에 관해 토론하던 중 동기가 낸 알고리즘이 정답이더라........

 

1. DP 문제는 몇 가지 후보군 중 최솟/최댓값과 현재 노드의 값을 더해 값을 결정하는 형식이 많으므로,

    주어진 것에서 최솟/최댓값을 뽑으려고 생각하지 말고,

    최솟/최댓값이 될 수 없는 것을 제외하는 방향으로 생각해 후보군을 좁히는 것도 방법.

2. 누적합의 최소를 구하는 문제이므로 그 순간에서 최솟/최댓값을 구하는 Greedy 방식으로 푸는 것은 의미 없을 수 있다.

     각각의 최솟/최댓값을 선택하려하지 말고 누적합의 후보들 중 최솟/최댓값을 선택하도록 생각할 것.

     그러려면 누적값으로 후보를 만들어야한다.