RGB거리2[백준 17404] - python

 

너무 어려웠다.

결국 다른 분들의 잘 짜신 코드를 참고했다. ㅠㅠ

정답코드 먼저 살펴보자

 

n = int(input())
cost = []
INF = 1e9

for _ in range(n):
  cost.append(list(map(int, input().split())))

result = INF

for start_number in range(3) :
  dist = [[0] * 3 for _ in range(len(cost))]

  for i in range(3) :
    if i != start_number :
      dist[0][i] = INF
    else :
      dist[0][i] = cost[0][i]

  for i in range(1, len(cost)):
    dist[i][0] = min(dist[i-1][1], dist[i-1][2]) + cost[i][0]
    dist[i][1] = min(dist[i-1][0], dist[i-1][2]) + cost[i][1]
    dist[i][2] = min(dist[i-1][0], dist[i-1][1]) + cost[i][2]

  for i in range(3) :
    if i != start_number :
      result = min(result, dist[n-1][i])

print(result)

 

rgb거리1 에서 조건이 하나 추가되어서 원형 테이블과 같은 형태를 띄게 된건데 생각이 전혀 안났었다. (다음엔 잘 풀기 위해서 잘 정리해두자)

 

1. 첫번째 라운드에 무슨 색깔을 칠할지 강제하자 (ex. 빨간색을 칠할경우에 초록, 파랑색을 매우 큰값을 넣어주자)

    1-1. (ex. 이렇게 하면 첫번째에 파랑, 초록을 선택한 경우는 라운드를 거듭할수록 도태된다.)

2. 마지막 라운드에서 첫번째 라운드에 색칠한 값을 제외한 값들중 최솟값을 선택해주자(ex. 1라운드에 빨강을 칠했다면 마지막 라운드에서는 초록, 파랑중에 선택을 하자)

 

이러면 총 비교해야 하는 경우의 수는 6가지다.

1. 1라운드 빨강, 마지막 라운드 초록
2. 1라운드 빨강, 마지막 라운드 파랑
3. 1라운드 초록, 마지막 라운드 빨강
4. 1라운드 초록, 마지막 라운드 파랑
5. 1라운드 파랑, 마지막 라운드 빨강
6. 1라운드 파랑, 마지막 라운드 초록

 

dp는 어렵다...

 

 

 

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

17404번: RGB거리 2