백준 2579, 11057 - JAVA

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

2579번: 계단 오르기

(출발지점)	10	20	15	25	10
				i (현재 위치)

- 한번에 한칸 또는 두칸 이동이 가능하며 세칸을 연달아 올라갈수는 없다. 

- DP 배열은 각 칸에서 가질 수 있는 최대 점수로 잡았다. 

- 만약 i가 25에 있다고 가정해보자 

- 이경우 DP[i-3] (표의 10) + stairs [i-1] (표의 15) 또는 DP [i-2] 이 2가지 케이스 중 선택하게 된다.

- DP[i-1]을 사용하지 않는 이유는, 여기 저장된 값 자체만으로는 이전 계단(20)을 밟았는지 안밟았는지 모르므로 현재 25를 밟을 수 있는지 없는지 모른다. 

- 따라서 3칸 전 까지의 DP값 + 바로 직전 값을 밟는 것 , 그리고 2칸 전까지의 최댓값(직전값은 안밟은것으로) 2가지중 최대를 고른 후, 현재 위치의 계단 값을 더해서 구해야 한다. 

 

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

public class p2579 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[] DP = new int[num+1];
        int[] stairs = new int[num+1];

        for (int i = 1; i <= num; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }
        DP[1] = stairs[1];
        if (num >= 2) {
            DP[2] = stairs[1] + stairs[2];
        }

        for (int i = 3; i <= num; i++) {
            DP[i] = Math.max(DP[i-2], DP[i-3] + stairs[i-1]) + stairs[i];
        }
        System.out.println(DP[num]);
    }
}

 

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

11057번: 오르막 수

DP를 이차원 배열로 정의하였다.

이 오르막 수의 규칙은 1자리일 때는 10, 2자리일때는 (10+9+...+1) = 55, 3자리일때는 (1 + 4 + 10 + ... 55) = 220...

이런식으로 n 자릿수의 오르막수 개수는 n-1자릿수를 가지고 구할 수 있다

아래 표의 1열의 마지막 행은 10, 2열의 마지막 행은 55... 즉 이차원 배열의 마지막 행값이 해당 자릿수의 오르막 수 개수가 된다. 

그리고 각 칸은 자신의 위쪽 값 + 왼쪽 값으로 구할 수 있다. 

즉, DP[i][j] = DP[i-1][j] + DP[i][j-1]  이라는 점화식을 세울 수 있다. 

1	2	3	4	5	6	7	8	9	10
1	3	6	10	15	21	28	36	45	55
1	4	10	20	35	56	84	120	165	220
1	5	15	35	70	126	210	330	495	715
1	...

 

import java.util.Scanner;
public class p11057 {
    public static void main(String[] args) {
        final int DIV = 10007;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] DP = new int[n][11];
        for (int i = 1; i <= 10; i++) {
            DP[0][i] = i;
        }

        for (int i = 0; i < n; i++) {
            DP[i][1] = 1;
        }

        for (int r = 1; r < n; r++) {
            for (int i = 2; i <= 10; i++) {
                DP[r][i] = ((DP[r-1][i] % DIV) + (DP[r][i-1] % DIV)) % DIV;
            }
        }

        System.out.println(DP[n-1][10]);
    }
}