Algorithm, boj, 2579(계단오르기), dp

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

• 주어진 문제를 여러 개의 부분문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다
• dp는 겹치는 문제가 발생하기 때문에 메모제이션 등이 필요하다
  

  문제 풀이

• 마지막 계단의 최대 점수를 구하는 DP문제이다
• 첫번째 계단을 밟았을때 최대 값은 첫번째 계단을 밟았을 때 받게 되는 점수이다. sum[1] = step[1];
• 두번째 계단을 밟았을때 최대 값 : 첫번째 계단을 밟고 두번째 계단 밟았을때 or 곧 바로 두번째 계단 밟았을때 이다
• 세번째 계단을 밟았을때 최대 값 : 첫번째 계단 + 세번째 or 두번째 계단 + 세번째
• n번째 계단을 밟았을때 최대 값 : n-3번째 계단에서 n-1번까지 점프 후, n번째 계단으로 or n-2번째 계단에서 n번째 계단으로

 package org.baekjoon;

 import java.util.Scanner;

 public class test2579 {

 	public static void main(String[] args) {
 		// TODO Auto-generated method stub

 		Scanner sc = new Scanner(System.in);
 		int stair[] = new int[300+1];
 		int n = sc.nextInt();
 		for (int i=1; i<=n; i++) {
 			stair[i] = sc.nextInt();
 		}

 		int sum[] = new int[stair.length];


 		for (int i = 1; i <= 3; i++) {
 		    if (i != 3) { //세번째까지 도달하지 않았을 경우 1번째 계단  + 2번째 계단
 		        sum[i] = sum[i-1] + stair[i];
 		    }
 		    else {
 		    	sum[i] = Math.max(sum[i-2] + stair[i], stair[i] + stair[i-1] );
 		    }
 		}

 		for (int i = 4; i <= n; i++) {
 			sum[i] = Math.max(sum[i-3] + stair[i-1] + stair[i], sum[i-2] + stair[i]);
 		}
 		System.out.print(sum[n]);
 	}

 }

---

Reference

문제바로가기 문제풀이