[백준] 11048번 이동하기 (Go)

이동하기

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

---

풀이

먼저, 이 문제의 카테고리는 동적 계획법(Dynamic Programming)인데요!

동적 계획법이란 특정 범위까지의 값을 구하기 위해 이전의 값을 사용해 효율적으로 값을 구하는 알고리즘이에요. 이전의 답을 재활용해서 원하는 값을 얻을 수 있는 방법이죠!

 

이동하기는 준규가 (N, M)까지 이동하면서 가장 많은 사탕을 가져와야하는 문제입니다. 동적 계획법을 활용해 풀었을 때, 만약, (N, M)이 (1, 1)이라면, (0, 0), (0, 1), (1, 0) 중 가장 큰 수를 지나와야 답이겠죠.

그럼 만약, (N, M)이 (2, 2)일 때, (1, 1)로 올 때처럼 계산을 하고 그 위치에 사탕의 개수를 저장시키면, (1, 1), (1, 2), (2, 1)은 가질 수 있는 가장 많은 사탕의 값을 가지게 됩니다! 그리고 (2, 2) 위치에 왔을 때 (1, 1), (1, 2), (2, 1) 중 가장 큰 수를 지나오게 되면 준규가 가질 수 있는 가장 큰 사탕의 수가 되죠.

package main

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

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	var n, m int
	fmt.Fscan(r, &n, &m)

	candies := make([][]int, n)

	for x := 0; x < n; x++ {
		for y := 0; y < m; y++ {
			var count int
			fmt.Fscan(r, &count)

			values := [3]int{0}

			if x != 0 {
				values[0] = candies[x-1][y]
			}
			if y != 0 {
				values[1] = candies[x][y-1]
			}
			if x != 0 && y != 0 {
				values[2] = candies[x-1][y-1]
			}

			count += max(values)

			candies[x] = append(candies[x], count)
		}
	}

	fmt.Fprint(w, candies[n-1][m-1])
}

func max(values [3]int) int {
	var t int

	for _, v := range values {
		if t < v {
			t = v
		}
	}

	return t
}