[Python, 백준] 1149번 : RGB거리

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

1149번: RGB거리

 

 

처음에는 손코딩으로 해봤는데 접근방법을 완전 잘못 잡았다 ^^...

DP로 풀면 훨씬 낫다는걸 나중에 깨달아서 손코딩으로 푼건 의미가 없었다고...

DP로는 그냥 pycharm에서 풀었음

---

방법 1. 

처음에는 그냥 생각나는대로 구현함

1. input 받아서 2차원 배열에 넣은 다음

2. 행의 최소값이 이전 행의 최소값의 인덱스와 같으면 정답값에 더한다

def solution():
    house_num = int(input())
    rgb_array = []
    answer = 0

    for i in range(house_num):
        rgb_data = str(input())
        rgb_array += [rgb_data.split()]

    prev_idx = []
    for data in rgb_array:
        # 최소값의 인덱스가 이전 최소값의 인덱스와 같으면
        if data.index(min(data)) != prev_idx:
            #print(data.index(min(data)), min(data))
            answer += int(min(data))
            prev_idx = data.index(min(data))
        else:
            data.pop(prev_idx)
            answer += int(min(data))
            prev_idx = data.index(min(data))

    print(answer)

solution()

예제 답변은 맞았지만 제출했을때 자꾸 틀렸습니다!! 가 나오길래 반례를 찾아봤음 

5
5 5 5
4 1 1
5 3 5
4 5 2
1 3 5

위와 같이 중복 값이 들어가는 경우에는 앞에 나오는 값을 선택하게 돼서

최적루트가 아니라 그냥 앞순서로 나오는 숫자(색상)를 선택하게 되어버림

 

원하는 순서 : 5 -> 1 -> 3 -> 2 -> 1 / 답 :12

실행되는 순서 : 5 -> 1 -> 5 -> 2 -> 1 / 오답 :14

---

방법 2. 

DP 로 풀었더니 훨씬 깔끔하고 좋았다.

def solution():
    n = int(input())
    rgb_array = []
    for i in range(n):
        rgb_array.append(list(map(int, input().split())))

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

	print(min(rgb_array[n - 1][0], rgb_array[n - 1][1], rgb_array[n - 1][2]))

solution()

위에 입력받는 부분에서

list(map(int, input().split())을 썼더니 input 받아서 바로 int 배열에 예쁘게 넣을 수 있었음

---