[BOJ] 1149 - RGB 거리

문제

---

문제링크

문제 분석

---

위 조건들을 종합해보면, 인접한 집의 색깔은 달라야 한다.

알고리즘 전략

---

처음에는 완전탐색을 생각했다.

• 첫 번째 집에 빨강을 칠하는 경우 ~ 완전탐색
• 첫 번째 집에 초록을 칠하는 경우 ~ 완전탐색
• 첫 번째 집에 파랑을 칠하는 경우 ~ 완전탐색

로직을 구현하려 하니 너무 복잡했다. n번 째 집을 선택할 때마다 새로 고려해야 하는 경우의 수가 2의 n제곱 이 되어버려서 N 의 범위 (1<= N <=1000)에 맞지 않는 풀이법이라 판단했다.

어차피 N번째 선택은 N-1번째의 선택(직전의 선택 케이스)만 고려하면 되는 것 아닌가?

이 문장을 다시 한 번 생각해보면, 이런 의미로 생각을 확장시킬 수 있다.

N번째 집을 색칠할 때 N번째 집을 가장 싸게 칠할 수 있는 색을 선택하면 되지 않을까?

하지만 이것은 틀렸습니다!

왜냐? N+1번째 집을 색칠하는 비용에 따라 N번째 집을 조금 비싼 색으로 칠할 수도 있기 때문이다.

-	R	G	B
N=1	100	200	300
N=2	200	400	600

N을 1번 집까지 칠하기 위한 최소비용은 말 할 것도 없이 'R'(100)이다.
그렇지만 N을 2번 집까지 칠할 때도 1번 집을 'R'로 칠해야할까?

아니다. 1번 집을 'G'(200) 으로 칠하고, 2번 집을 'R'로 칠하는 것이 400으로 최소비용의 선택이다.

미래에 어떤 선택을 하냐는 과거에 영향을 받는다.

어라? 그러면 각 집에서의 최소비용을 단일로만 고려하는 건 의미가 없네?

맞다. 우리의 풀이는 n번째 집에 대해서 하나의 색깔을 고르는 것이 아니라, 세 가지 선택을 이전 값과 함께 모두 고려하는 풀이를 진행해야 한다.

즉, 단일비용이 아닌, 누적비용을 고려해야 하는 것이다.

n번째 집에서 R을 선택하는 경우의 누적된 비용,n번째 집에서 G을 선택하는 경우의 누적된 비용,n번째 집에서 B를 선택하는 경우의 누적된 비용 이 세 가지 말이다.

이 세 가지를 알아야 최종적으로 n번째 집까지 색을 칠하는 최소비용을 고려할 수 있을 것이다.

n번째 집까지 x색상을 선택하는 경우의 최소비용은 n-1번째 집까지 얼마나 비용이 쌓였나를 고려해야한다. 즉, 현재 선택에 과거까지 쌓인 데이터를 어디엔가 기록하고 활용해야하므로 별도의 메모리공간에 저장할 필요가있다.

즉 DP문제였다. 그리고 한 번에 3가지의 선택결과를 다 저장해야 하니 2차원 배열의 메모이제이션 테이블이 필요하다.

비용테이블

-	R	G	B
N=1	100	200	300
N=2	200	400	600
N=3	200	50	10

누적 테이블

-	R을 선택	G를 선택	B를 선택
N=0까지누적비용	0	0	0
N=1까지누적비용	100	200	300
N=2까지누적비용	200+200	400+100	600+100
N=3까지누적비용	400+100+200	200+200+50	200+200+10

N=1인경우부터 살펴보자.
이 경우는 누적 테이블에 그대로 선택값을 넣어주면된다.

N=2인 경우를 보자.

• N=2에서 R을 선택하는 경우.

  • N=1까지 누적된 비용들 중, G를 선택한경우와, B를 선택한 경우가 N=2에서 R을 선택할 수 있다.

  • 인접한 집은 같은 색상을 칠할 수 없으니까 말이다.

  • 따라서 둘 중 최소값을 선택하여 비용테이블의 (N=2, 'R')에 해당하는 값과 더하여 누적테이블을 업데이트시켜준다.

아하...이후에도 동일하게 테이블을 채운다.

정답은 그러면 누적테이블의 N번째 row에서 최소값을 찾으면되겠다.

잡생각

---

성공한 풀이

---

위 문제해결 아이디어를 그대로 구현해보자.

const directory = process.platform === 'linux' ? 0 : __dirname + '/test.txt'
const input = require('fs').readFileSync(directory).toString().trim().split('\n')
const N = input[0] * 1

const dpTable = Array.from({ length: N + 1 }, () => Array.from({ length: 3 }, () => 0))

for (let i = 1; i < N + 1; i++) {
  const [R, G, B] = input[i].split(' ').map(Number)
  const [prevAccR, prevAccG, prevAccB] = dpTable[i - 1]
  dpTable[i][0] = R + Math.min(prevAccG, prevAccB)
  dpTable[i][1] = G + Math.min(prevAccR, prevAccB)
  dpTable[i][2] = B + Math.min(prevAccR, prevAccG)
}

console.log(Math.min(...dpTable[N]))