백준 2579번 - 계단 오르기

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

2579번: 계단 오르기

---

위 문제에서 무조건 마지막 계단은 밟아야하므로 모든 구하려는 값에 마지막 계단의 수를 더해야 한다. 

 

첫 번째 계단의 점수를 score[1]

두 번째 계단의 점수를 score[2]

...

이런 식으로 구성하고

 

계단이 1개일 경우의 총 점수의 최댓값 dp[1]

계단이 2개일 경우의 총 점수의 최댓값 dp[2]

...

 

이런 식으로 구성하였을 때 아래 사진과 같은 규칙을 보인다.

dp[1] = score[1]

dp[2] = score[1]+score[2]

dp[3] = score[1]+score[3] 또는 score[2]+score[3]

...

 

dp[4] 부터는 규칙을 이용하여 작성하면

for(int i=4;i<=n;i++)

{

dp[i]=Math.max(dp[i-3]+score[i-1], dp[i-2])+score[i];

}

 

 

 

dp[6]을 예로 들었을 때 위 사진과 같은 규칙을 보인다.

 

코드

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
	       Scanner sc = new Scanner(System.in);
	       int n = sc.nextInt();
	       int score[] = new int[301];
	       int dp[] = new int[301];
	       
	       
	       for(int i=1;i<=n;i++){
	    	   score[i]=sc.nextInt();
	       }
	    	   
	       dp[1]=score[1];
	       dp[2]=score[1] + score[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]);
	 }
}