[JAVA] 백준 2579 계단 오르기

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

2579번: 계단 오르기

 

- 계단 오르기 개임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 

- 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

 

 

- 계단 오르는 데는 다음과 같은 규칙이 있다. 

  

1) 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉 한 계단씩 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 

   

2) 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단 시작점은 계단에 포함되지 않는다. 

 

3) 마지막 도착 계단은 반드시 밟아야 한다. 

 

- 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램

 

 

풀이 과정 

 

[백준 - Java] 2579번 : 계단 오르기 (tistory.com)

[백준 - Java] 2579번 : 계단 오르기

[백준] 2579번 : 계단 오르기 - JAVA [자바] (tistory.com)

 

[백준] 2579번 : 계단 오르기 - JAVA [자바]

 

- 현재 인덱스 i에 대해 두 칸 전(i-2)의 '메모이제이션 값'과 첫 칸 전(i-1)의 값 +셋 째칸 전(i-3)의 '메모이제이션 값' 중 큰 값을 현재 i계단의 값과 합하여 memo 배열에 저장(Memoization)을 해주면 됨 

 

- Bottom-up을 이용한 동적 프로그래밍으로 풀이 

 

- 현재 계단이 i일 때

   1) 그 전 계단 i-1을 밟고 올라왔는지

       - memo[i-1] (전 단계) + memo[i-3] (점프 전 최대값) + memo[i] (현재 계단의 값)

 

   2) 그 전전 계단 i-2에서 왔는지 

       - memo[i-2] (점프한 최대값) +  memo[i] (현재 계단의 값)

 

    - 이 둘 중 큰 값을 memo[i]에 저장

 

- memo[0]과 memo[1]은 각각 첫 번째 계단과 두 번째 계단까지 점수의 합으로 초기화 

- 3번째 계단부터 n까지 for문을 통해 반복하며 memo를 갱신

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        int stairs[] = new int[n+1];
        int memo[] = new int[n+1];
        
        for(int i=1; i<=n; i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            stairs[i] = Integer.parseInt(st.nextToken());
        }
        
        memo[1] = stairs[1];
        
        //n이 1이 입력될 수도 있기 때문에 예외처리
        if(n>=2)
        {
            memo[2] = stairs[1] + stairs[2];
        }
        
        for(int i=3; i<=n; i++)
        {
            memo[i] = Math.max(memo[i-2], memo[i-3]+stairs[i-1])+stairs[i];
        }
        
        bw.write(memo[n]+"");
        
        bw.flush();
        bw.close();
        
    }
}