[Go] 백준 2579번 계단 오르기

문제

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

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여있는 점수가 주어진다. 계단의 개수는 300 이하의 자연수이고, 계단에 쓰여있는 점수는 10,000 이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총점수의 최댓값을 출력한다.

---

문제 풀이

문제 해석 및 계획

이전에 한 계단 올랐다면 다음에는 무조건 두 계단을 올라야 하고 이전에 두 계단 올랐다면 다음에는 한 계단 혹은 두 계단 오를 수 있습니다.

이전에 오른 계단의 개수에 따라 재귀함수를 불러옵니다.

오답 노트

예제와 추가적인 예제를 생각하여 시험한 결과 올바른 답을 출력하는 것을 확인하였습니다.

하지만 시간 초과 문제가 발생하였습니다.

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)
	pointList := make([]int, N)
	for i:=0 ; i<N ; i++ {
		fmt.Fscan(reader, &pointList[i])
	}


	rst1 := process(pointList, 0, 0, N-1)
	rst2 := process(pointList, 1, 0, N-1)

	if rst1 < rst2 {
		fmt.Fprintln(writer, rst2)
		return
	}
	fmt.Fprintln(writer, rst1)
}

func process(pointList []int, now, pre, goal int) int {
	if now == goal {
		return pointList[goal]
	}
	if now > goal {
		return 0
	}
	rst1 := 0
	rst2 := 0
	if pre != 1 {
		rst1 = process(pointList, now+1, 1, goal)
	}
	rst2 = process(pointList, now+2, 2, goal)

	if rst1 < rst2 {
		return pointList[now] + rst2
	}
	return pointList[now] + rst1
}

정답

재귀함수가 아닌 반복문을 통하여 해결할 방법을 고민하였습니다. i번째 계단에 오는 방법은 i-1에서 한 계단 오르는 방법과 i-2에서 두 계단 오르는 방법이 있습니다. i-1에서  계단을 오르기 위해서는 i-3에서 오는 방법만 존재합니다.

따라서 i번째의 최고 점수는 i-1까지의 최대 혹은 i-3까지의 최대 더하기 i-1 중에 더 큰 값과 i번째의 점수와 더하는 방법입니다.

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)
	pointList := make([]int, N)
	for i:=0 ; i<N ; i++ {
		fmt.Fscan(reader, &pointList[i])
	}

	maxPoint := make(map[int]int)
	maxPoint[0]=pointList[0]
	for i:=1 ; i<N ; i++ {
		max:=max(maxPoint[i-2],maxPoint[i-3]+pointList[i-1])
		maxPoint[i]=max + pointList[i]
	}
	fmt.Fprintln(writer, maxPoint[N-1])
}

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

---

느낀 점

재귀함수로 문제를 푸는 경우 대부분 시간초과에 걸리게 됩니다. 최대한 재귀함수가 아닌 방법으로 풀기 위하여 노력을 하고 최후의 수단으로 재귀함수를 선택하는 방식으로 문제를 푸는 노력이 필요하다고 느끼게 되었습니다.