acmicpc

[BAEKJOON] 2579. 계단 오르기

코드와이 2021. 2. 19. 16:52

 

DP문제

문제풀이

www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

 

package acmicpc.Silver3;

import java.util.Scanner;

public class 계단_오르기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] sta = new int[301];
		int n = sc.nextInt();
		
		if( n == 1) {
			System.out.println(sc.nextInt());
		}
		else {
			for(int i = 1 ; i <= n ; i++) {
				sta[i] = sc.nextInt();
			}
			int[] ans = new int[301];
			ans[1] = sta[1];
			ans[2] = sta[2] + sta[1];
			for(int i = 3 ; i <= n ; i++) {
				ans[i] = Math.max(sta[i] + sta[i-1] + ans[i-3], sta[i] + ans[i-2]);
			}

			System.out.println(ans[n]);
		}
		sc.close();
	}
}