#2579 : 계단 오르기

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

 

2022.03.15

k번째 계단에 도달하는 방법의 수는 다음의 두 가지가 있다.

각 계단에 대하여,

해당 계단까지 도착하는 위의 두 가지 방법 중

더 큰 점수를 모아올 수 있는 쪽을 선택하면 된다.

 

이 방법을 이용하여,

각 계단마다

각각의 계단에 도달하기까지 모아올 수 있는 최대의 점수를 각각 구한다.

나는 이 값을 max_score[] 배열에 저장하였다. (max_score[i] = i번째 계단에 도달하기까지 모아올 수 있는 최대의 점수)

그럼 max_score[마지막 계단의 번호]의 값이 바로 정답이다.

코드

Java(2022.03.15)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int n;	//계단의 개수
	static int[] init_score;	//각 계단별 원래 할당된 점수
	static int[] max_score;	//각 계단별 그 계단에 오기까지 모아올 수 있는 최대의 점수
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//계단 개수 읽어오기
		n = Integer.parseInt(br.readLine());
		init_score = new int[n+1];
		max_score = new int[n+1];
		//계단별로 할당된 점수 읽어오기
		for(int i = 1; i<n+1; i++)	init_score[i] = Integer.parseInt(br.readLine());
		//max_score 배열에 데이터 채우기
		max_score[1] = init_score[1];
		if(n>1) {
			max_score[2] = init_score[1] + init_score[2];
			
			if(n>2) {
				for(int i = 3; i<n+1; i++)
					max_score[i] = Math.max(max_score[i-3] + init_score[i-1], max_score[i-2])+init_score[i];
			}
		}
		
		//정답 출력
		System.out.print(max_score[n]);
		
	}

}

if(n>1), if(n>2) 조건문이 있는 것은, 계단의 총 크기가 1 혹은 2일 경우 발생할 수 있는 ArrayIndexOutOfBounds 오류를 예방하기 위해서이다.

 

Java(2022.03.15, E-PPER 제출을 위한 solution 함수 형식)

	public static int solution(int n, int [] score) {
		int answer = 0;
		
		int[] max_score = new int[n+1];
	
		max_score[1] = score[1];
		if(n>1){
			max_score[2] = score[1] + score[2];
			if(n>2){
				for(int i = 3; i<n+1; i++){
					max_score[i] = Math.max(max_score[i-2], max_score[i-3] + score[i-1]) + score[i];
				}
			}
		}	
		answer = max_score[n];
		return answer;
	}