백준(BOJ) 2579 : 계단 오르기 (실버3) / 자바(Java) 풀이

문제

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

3줄 요약

• 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 구하기 위해 다음과 같은 점화식을 세웁니다.
  • memo[i] = max(memo[i-3] + stairs[i-1], memo[i-2]) + stairs[i]
  • 현재 계단을 밟을 때, 이전에 밟은 계단이 i-3번째 계단인 경우와 i-2번째 계단인 경우 중 더 큰 점수를 선택하여 현재 계단의 점수를 더합니다.
• 메모이제이션 기법을 사용하여 이전에 계산된 값을 저장하고 재사용함으로써 중복 계산을 피하고 효율성을 높입니다.
  • memo 배열을 사용하여 각 계단까지의 최대 점수를 저장합니다.
  • 점화식을 이용하여 계산할 때, 이미 계산된 값은 memo 배열에서 가져와 사용합니다.
• 최종적으로 memo[n]에 저장된 값이 n개의 계단을 올랐을 때 얻을 수 있는 총 점수의 최댓값이 되며, 이를 출력합니다.

코드

// package boj2579;

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력 파일에서 데이터 읽기 (테스트용)
        // System.setIn(new FileInputStream("src/input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 계단의 개수 n 입력받기
        int n = Integer.parseInt(br.readLine());
        
        // 계단의 점수를 저장할 배열 초기화
        int[] stairs = new int[n + 1];
        
        // 계단의 점수 입력받기
        for (int i = 1; i <= n; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }
        
        br.close();
        
        // 메모이제이션을 위한 배열 초기화
        int[] memo = new int[n + 1];
        
        // 초기 값 설정
        memo[1] = stairs[1];
        if (n >= 2) {
            memo[2] = stairs[1] + stairs[2];
        }
        
        // 동적 계획법을 이용하여 최대 점수 계산
        for (int i = 3; i <= n; i++) {
            memo[i] = Math.max(memo[i - 3] + stairs[i - 1], memo[i - 2]) + stairs[i];
        }
        
        // 결과 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Integer.toString(memo[n]));
        bw.flush();
        bw.close();
    }
}