[백준] 2579번 계단 오르기 JAVA (자바) 풀이

문제 2579번 (DP)

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

 

계단 오르는 규칙

1. 한 번에 한 계단씩 또는 두 계단씩 오르기
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다 (단, 시작점은 미포함)
3. 마지막 도착 계단은 반드시 밟아야 한다

총 점수의 최댓값을 구하는 프로그램을 작성하시오

 

 

 

 

[입력]

 :  입력의 첫째 줄에 계단의 개수

    둘째 줄부터 한 줄에 하나씩 계단 점수

    (계단 개수는 300이하의 자연수, 계단 점수는 10,000이하의 자연수)

 

[출력]

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

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1. N인 현위치는 무조건 밟아야 한다

• 현위치는 반드시 밟아야 하므로 이전 계단에서 어느부분을 건너 뛸 지 고민하기
• 이전 3개의 계단에서 2칸씩 뛰어서 올 것인지 1칸-3칸 번갈아가며 올 것인지 결정
  • dp[4] 
  • dp[i-2] = dp[2] 두칸씩 뛰어 현지점 도착
  • dp[i-3] + score[i-1] = dp[1] + score[3] 1번째 계단에서 3번째 계단으로 갔다가 현지점 도착

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int score[] = new int[N+1];
        int dp[] = new int[N+1];
        
        for(int i=1;i<=N;i++){
            score[i] = Integer.parseInt(br.readLine());
        }
        
        dp[1] = score[1];
        if(N>1) dp[2] = score[1]+score[2];
        if(N>2) dp[3] = Math.max(score[1], score[2]) + score[3];
        for(int i=4;i<=N;i++){
            dp[i]= Math.max(dp[i-3]+score[i-1], dp[i-2]) + score[i];
        }
        
        System.out.println(dp[N]);
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int score[] = new int[N+1];  계단점수 입력 따로 받기
    int dp[] = new int[N+1];  dp 배열 
        
 :  for(int i=1;i<=N;i++){  계단 1부터 점수 계산
            score[i] = Integer.parseInt(br.readLine()); 
    }
        
 :  dp[1] = score[1];  1번 계단
    if(N>1) dp[2] = score[1]+score[2];  1-2 연속 계단
    if(N>2) dp[3] = Math.max(score[1], score[2]) + score[3]; 1-3 계단 / 2-3 계단 중 최대값
    for(int i=4;i<=N;i++){  계단 4부터 계산
            dp[i]= Math.max(dp[i-3]+score[i-1], dp[i-2]) + score[i];  

            현재 계단을 제외하고 이전 계단까지 생각했을 때
            연속된 3개중 1번째 3번째 밟고 현위치로 올 건지

            2번째 밟고 현위치로 올 건지 고민
    }
        
 :  System.out.println(dp[N]);  결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

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

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *