[Go] 백준 1149 RGB거리 (Dynamic Programming)

문제

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

입력

첫째 줄에 집의 수 N (2 <= N <= 1000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

---

문제 풀이

문제 해석 및 계획

첫 번째 집의 색을 정하고 다음에 올 집의 색 중에 저렴한 생상을 고르는 순서를 생각하였지만 지금 집에 저렴한 색상의 가격을 골랐을 때 다음에 올 집의 저렴한 색상과 겹치는 문제가 발생하였습니다.

로직을 고민하기 위하여 가장 기초적으로 재귀함수를 이용하였습니다.

오답 노트

다양한 방법을 생각해 보았지만 재귀함수를 이용하는 방법만 떠올랐습니다. 시간초과가 될 것이라고 예상하였지만 혹시 하는 마음에 도전하였고 당연히 실패하였습니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var N int
	fmt.Fscan(reader, &N)

	houses := make([][3]int,N)
	for i:=0 ; i<N ; i++ {
		fmt.Fscan(reader, &houses[i][0], &houses[i][1], &houses[i][2])
	}
	answer := 1000*N
	for i:=0 ; i<3 ; i++ {
		rst := calc(houses, 0, i)
		if rst < answer {
			answer = rst
		}
	}
	fmt.Fprint(writer, answer)
}

func calc(houses [][3]int, idx, color int) int {
	if idx >= len(houses){
		return 0
	}
	rst1 := calc(houses, idx+1, (color+1)%3)
	rst2 := calc(houses, idx+1, (color+2)%3)
	if rst1 < rst2 {
		return houses[idx][color] + rst1
	}
	return houses[idx][color] +rst2
}

정답

도무지 방식이 떠오르지 않아 힌트를 찾아본 결과 Dynamic Programming이란 것을 알게 되었습니다.

새로운 언어를 배울 때면 항상 피보나치수열 계산기를 만들어 보았는데 이때 재귀함수가 아닌 방법으로 풀는 방식이 Dynamic Programming이라고 합니다. 줄여서 DP라고도 부릅니다.

피보나치 수열이라는 힌트를 알게 되니 방법이 떠올랐고 아래와 같이 작성하여 해결하였습니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)

	defer writer.Flush()

	var N int
	fmt.Fscan(reader, &N)

	houses := make([][3]int,N)
	for i:=0 ; i<N ; i++ {
		fmt.Fscan(reader, &houses[i][0], &houses[i][1], &houses[i][2])
	}
	sum := make([][3]int,N)
	sum[0] = houses[0]
	for i:=1 ; i<N ; i++ {
		for j:=0 ; j<3 ; j++ {
			sum[i][j] = houses[i][j] + min(sum[i-1][(j+1)%3], sum[i-1][(j+2)%3])
		}
	}
	answer := min(sum[N-1][0], sum[N-1][1])
	answer = min(answer, sum[N-1][2])

	fmt.Fprint(writer, answer)
}

func min(a, b int) int {
	if a < b{
		return a
	}
	return b
}

---

느낀 점

피보나치수열과 다를 것이 없는 문제였습니다. 단지 덧셈을 하는 경우의 수가 늘어나고 결과가 3가지라는 점이 다를 뿐 원리만 이해한다면 쉽게 풀 수 있는 문제였습니다.

시간을 줄이기 위하여 한번에 해결되는 로직을 생각하다 보니 단순한 방법을 보지 못하였습니다. 항상 침착하게 생각하고 이전의 로직들을 기억하여 활용할 수 있도록 준비하여야겠다고 느꼈습니다.