문제는 더보기!
문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
예제 입력 1 복사
3 26 40 83 49 60 57 13 89 99
예제 출력 1 복사
96
예제 입력 2 복사
3 1 100 100 100 1 100 100 100 1
예제 출력 2 복사
3
예제 입력 3 복사
3 1 100 100 100 100 100 1 100 100
예제 출력 3 복사
102
예제 입력 4 복사
6 30 19 5 64 77 64 15 19 97 4 71 57 90 86 84 93 32 91
예제 출력 4 복사
208
예제 입력 5 복사
8 71 39 44 32 83 55 51 37 63 89 29 100 83 58 11 65 13 15 47 25 29 60 66 19
예제 출력 5 복사
253
처음에 살짝 헤맸었다.. 조합을 다 보자니 경우의 수가 너무 많고 해서 처음에는 현재줄과 다음줄을 본 후에 계산해서 적용하려고 했는데 머릿속으로 생각해도 계속 예외가 생겼다.
고민하다가 생각해낸건 리스트를 하나 만든다음에, 1번째 줄까지의 최소, 2번째 줄까지의 최소값 이런식으로 천천히 채워나가면 되지 않을까? 란 생각이 들었는데 그것또한 구현하기가 쉽지 않았다.
RGB중 어디서 시작하는지 정하는게 쉽지 않았기 때문이다. 여기서 고민을 계속하다가 결국 인터넷의 도움을 조금 받았는데.. RGB중 어디서시작하는지 모르니까 3개를 다해보면 되는 것이었다.. 어차피 그래봤자 for문 1번을 3개씩 돌리는 거니까..
2번째 줄부터 시작해서 생각해보자, R G B 중 R을 선택했다고 치면 1번째 줄에서는 G와 B중 하나를 택할 수 있단 뜻이다. 그렇다면 G,B 중에서 더 작은값을 R값에 구한다면, 2번째줄에서 R을 선택했을때의 최소값이 나오게 된다. 같은 방식으로 2번째 줄까지의 R,G,B각각을 택했을 때의 최소값을 구할 수 있다.
자 그러면 해당 배열의 2번째 줄의 값은 2번째 집을 칠하는 비용이 아닌, 2번째집까지 칠했을때의 최솟값들이 남아있게 된다. 여기서 3번째 집을 가서 같은 과정을 거치면 된다.
3번째 집을 R로 칠했을때 2번째집까지 칠했던 비용들을 합치게되고, 이 과정이 반복되면 결국 마지막집을 R,G,B로 칠했을때의 각각의 최소값이 남아있게 된다.
즉, 마지막 배열의 값중 최솟값을 뽑아내면 답을 구할 수 있다.
import sys
N = int(sys.stdin.readline())
lst = [ list(map(int,sys.stdin.readline().split())) for _ in range(N) ]
for i in range(1, N):
lst[i][0] += min(lst[i-1][1], lst[i-1][2])
lst[i][1] += min(lst[i-1][0], lst[i-1][2])
lst[i][2] += min(lst[i-1][0], lst[i-1][1])
print(min(lst[-1]))
'Python > 백준' 카테고리의 다른 글
1463_1로만들기 (0) | 2021.12.28 |
---|---|
1932_정수 삼각형 (0) | 2021.12.24 |
9461_파도반 수열 (0) | 2021.12.22 |
1904_01타일 (0) | 2021.12.21 |
1003_피보나치 함수 (0) | 2021.12.18 |