출처 : 백준, https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
내가 푼 게 아니다.....
풀이
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 | |
49 | 60 | 57 |
13 | 89 | 99 |
2. 남은 2개 중 더할 수 있는 것끼리 더한다.
앞서 제외된 열은 남은 열 중 작은 값과 더한다.
26 | 40 | |
49 + 40 | 60 + 26 | 57 + min(26, 40) |
13 | 89 | 99 |
3. 남은 행에 대해 반복한다.
26 | 40 | |
86 | 83 | |
13 + min(83, 86) | 89 + 83 | 99 + 86 |
4. 끝난 후 마지막 행 중 최솟값을 뽑는다.
26 | 40 | |
86 | 83 | |
96 | 172 | 185 |
시간 복잡도
-
다른 사람의 풀이를 보면서 알게 된 점
-
고찰
DP 문제는 점화식을 도출하는 문제인데, 너무 식으로만 도출하려해서 그런지 아이디어가 떠오르지 않았고,
동기와 문제에 관해 토론하던 중 동기가 낸 알고리즘이 정답이더라........
1. DP 문제는 몇 가지 후보군 중 최솟/최댓값과 현재 노드의 값을 더해 값을 결정하는 형식이 많으므로,
주어진 것에서 최솟/최댓값을 뽑으려고 생각하지 말고,
최솟/최댓값이 될 수 없는 것을 제외하는 방향으로 생각해 후보군을 좁히는 것도 방법.
2. 누적합의 최소를 구하는 문제이므로 그 순간에서 최솟/최댓값을 구하는 Greedy 방식으로 푸는 것은 의미 없을 수 있다.
각각의 최솟/최댓값을 선택하려하지 말고 누적합의 후보들 중 최솟/최댓값을 선택하도록 생각할 것.
그러려면 누적값으로 후보를 만들어야한다.
'알고리즘 > Python' 카테고리의 다른 글
[python] 백준 1072 - 게임 (0) | 2022.04.07 |
---|---|
[python] 백준 2193 - 이친수 (0) | 2022.04.03 |
[python] 백준 24460 - 특별상이라도 받고 싶어 (0) | 2022.04.03 |
[python] 백준 15657 - N과 M (8) (0) | 2022.03.28 |
[python] 백준 15656 - N과 M (7) (0) | 2022.03.28 |