[백준/BOJ] 백준 코딩 알고리즘 1149번 RGB거리 Python

문제

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

 

풀이

본 풀이 방법은 문제를 (i-1, i) 단위로 쪼개어 접근하고, 이전의 색칠 비용값을 누적해서 저장해나감으로써 해결한다

1. rgb 배열에 각 집의 색상을 빨강, 초록, 파랑으로 칠하는데 드는 비용을 입력받는다
2. 2번째 집부터 for문을 돌면서 i번째 집과 i-1번째 집을 칠하는데 드는 비용을 비교한다
3. 비용 비교는 다음과 같다. 
- i번째를 빨간색으로 칠할때: i-1번째를 초록색으로 칠하는 비용 vs i-1번째를 파란색으로 칠하는 비용
- i번째를 초록색으로 칠할때: i-1번째를 빨간색으로 칠하는 비용 vs i-1번째를 파란색으로 칠하는 비용
- i번째를 파란색으로 칠할때: i-1번째를 빨간색으로 칠하는 비용 vs i-1번째를 초록색으로 칠하는 비용
4. 위 과정을 가장 마지막 집까지 반복하며 각 색칠 경우에 따라 최소 비용을 업데이트해나간다.

 

생각했던 것

개인적으로 이 문제에서 가장 헷갈렸던 부분은 문제를 어떻게 쪼개야 할지 혼란스러웠던 것 같다
i번째 집이 i-1번째, i+1번째 집와 색상이 동일하면 안된다는 조건을 고려해서 문제를 쪼갠 작은 단위를 (i-1, i, i+1) 이렇게 3개로 잡았는데, 여기서 홀수와 짝수라는 (문제 어디서도 등장한적 없는데 내가 스스로 불러온 재앙.. 아니..) 조건에 얽매여서 괜히 혼란스러웠던 것 같다 

더불어, R배열, G배열 B배열을 모두 따로 만들 생각이었는데, 다른 사람들의 풀이나 코드를 참고해보니, 2차원 배열로 만드는 것이 더 편리할 것 같아서 해당 방법을 사용하게 되었다

 

본 문제를 플면서 든 생각은 역시 문제를 어떻게 쪼개고 규칙을 찾을 지 아는 것이 중요한 것 같다는 것이다. 그리고 그만큼 아이디어를 효율적이고 편리한 방법으로 구현할 줄 아는 능력이 있는 것도 !

 

  

참고

https://namhandong.tistory.com/131