[BOJ 1149][백준 1149번] RGB거리 (파이썬 풀이)

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

1149번: RGB거리

 

🤔 문제 설명 및 입출력

---

 

 

✍ 접근 방법

---

DP로 푸는 문제가 확실한데, 아쉽게도 처음 문제를 봤을때는 그런 생각을 못하고 단순한 조합 문제으로 생각했었다.

중복을 허용하는 순열 리스트를 만들어놓고, 매 3번째 입력마다 순열 리스트를 이용해서 최소값을 구하여 지속적으로 결과값에 더해가는 방식으로 접근 했다.

 

얼핏 보면 괜찮은 접근법이지만, 이 접근법에는 2가지 큰 구멍이 있었다.

 

1. N이 3의 배수가 아닐 경우, 최소값을 출력하지 못한다.
2. 3개의 입력에 대한 최적의 경우만을 출력하여, 이후의 4번째,5번째...경우까지 고려한 선택을 하지 못한다. (비유하자면, 2보 전진을 위한 1보 후퇴를 하지 못한다. 진짜 상남자다🤣🤣🤣)

 

사실 2번 문제 때문에 처음부터 바퀴가 빠진 접근법이였는데, 아시다시피 내 풀이가 완전히 틀렸다는것을 깨닫고, 인정하여 다시 백지로 돌아가는것이 여간 쉬운 일이 아닌지라, 풀이에 꽤 많은 시간이 걸렸다.

 

문제의 핵심인 "이전 값과 중복되지 않은 값 중 최소 값 구한 후 전체 비용에 반영" 을 너무 지엽적으로 생각했던것 같다.

 

비록 완전 잘못 접근하긴 했지만, 최초에 시도한 방법도 아래에 박제해놓겠다. 여러분들은 제 풀이 보시고 이런 식으로 풀면 망하는구나~ 라고 생각해주시면 되겠습니다

 

👨‍💻 소스 코드

---

• 파이썬

 

오답 코드

# 3가지 색상을 문제의 조건에 맞추어 칠할 수 있는 모든 경우의 수
case = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0],[0,1,0],[0,2,0],[1,0,1],[1,2,1],[2,0,2],[2,1,2]]
N = int(input())
test = []
result = 0
memo = 0xffffffff # 이전 선택자 값 디폴트 값 <-- 입력이 3개 이하여도 풀이에는 필터됨
for _ in range(N):
    house = list(map(int,input().split()))
    test.append(house)
    mini = 0xffffffff # 최소 값 디폴트
    if len(test) == 3:
        for elem in case:
            cost = 0
            for idx in range(len(elem)):
                cost += test[idx][elem[idx]]
                # 가지치기 <-- mini가 cost보다 더 커지면, 해당 case는 더 살필 필요가 없다
                if cost > mini:
                    break

            if cost < mini:
                mini = cost
                memo = elem[2]

        result += mini
        test = []


# 출력전, 입력이 1,2 인 경우일때를 대비하여 한 번 더 최솟값 출력 과정을 적용

# 입력이 1개인 경우
if len(test) == 1:
    tem_lst = []
    for idx,value in enumerate(test[0]):
        if idx == memo:
            continue
        else:
            tem_lst.append(value)
    result += min(tem_lst)

# 입력이 2개인 경우
if len(test)==2:
    tem_lst = []

    for idx,value in enumerate(test[0]):
        if idx == memo:
            continue
        else:
            for idx2,value2 in enumerate(test[1]):
                if idx2 == idx:
                    continue
                else:
                    tem_lst.append(value+value2)

    result += min(tem_lst)
                    

print(result)

보기만 해도 냄새가 나는 코드입니다. 비슷한 코드들이 반복되고, 일회성 변수들도 많고...그리고 이전에 선택한 값을 잡을라고 enumerate를 많이 썼는데, enumerate가 생각보다 비싼 기능이라, 옳게 된 풀이법이라고 했어도 시간 초과가 나지 않았을까 싶습니다.

 

 

정답 코드

n = int(input())
memo = [] # DP list

for idx in range(n):
    memo.append(list(map(int,input().split())))

for i in range(1,len(memo)):
    # 이번 케이스에서 집을 0번 색으로 칠했을 때의 비용은, 이번에 0번으로 칠하는데 드는 비용 + 이전 케이스에서 1번색/ 2번색으로 칠했던 경우의 비용의 합이다.
    memo[i][0] = min(memo[i-1][1],memo[i-1][2])+memo[i][0] 
    # 위와 마찬가지, 집을 1번 색으로 칠했을 때의 비용은, 이번에 1번으로 칠하는데 드는 비용 + 이전 케이스에서 0번색/ 2번색으로 칠했던 경우의 비용의 합
    memo[i][1] = min(memo[i-1][0],memo[i-1][2])+memo[i][1]
    # 결국 memo 리스트는 i번째 집까지를 0,1,2번 색으로 칠했을때의 최소값을 나타내는 리스트가 된다.
    memo[i][2] = min(memo[i-1][0],memo[i-1][1])+memo[i][2]

# 그렇기 때문에, 마지막 값의 최소값을 출력해주면, 여태까지 누적되었던 색칠 비용의 최솟값이랑 동일하다.
# n-1이 마지막인걸 기억
print(min(memo[n-1]))

 

반면 정답 코드는, DP를 이용해서 간결하고 깔끔하게 구현하였습니다. memo라는 리스트는 처음에는 입력값을 전부 가지고 있는 리스트지만, 2번째 for문을 거치면서 i번째 집까지 칠할때의 색깔 별 최소값들로 이루어진 리스트로 바뀐다.

결국, memo[n-1] = [ n-1번째 집을 0번색으로 칠했을 때의 최소 비용 누적값 , n-1번째 집을 1번색으로 칠했을 때의 최소 비용 누적값 , n-1번째 집을 2번색으로 칠했을 때의 최소 비용 누적값] 이 되므로, min을 이용해서 총 비용 최소값을 출력하면 된다.

 

 

🔥 강평

---

DP 문제는 언제나 그렇지만, 처음에 팍 하고 떠오르는 스파크가 중요한 것 같다. DP 문제인걸 알아차리기만 하면, 금방 금방 풀 수 있는 문제인데, 그 생각이 떠오르지 않는다면야... 상당히 어려운 시간을 보내게 된다.

 

나름 DP 문제 꽤 풀었다고 생각했는데, 바로바로 풀이가 생각나지 않는걸 보아, 아직 갈 길이 먼 것 같다.

 

 

그렇지만, 이번 문제를 풀면서

 

-이전의 선택이 현재의 선택에 영향을 미치는 경우, DP 풀이를 고려해보자-

 

라는 교훈을 얻을 수 있었다. 이후, 문제 풀이할 때마다 한번씩 곱씹어보면서 문제 풀이를 한다면, 더 효율적으로 문제를 해결할 수 있지 않을까 생각이 든다.