백준 알고리즘 10844번 동적계획법 기초

동적계획법(Dynamic Programming) 기초

자릿수 N을 입력 받고

  총 가질 수 있는 계단수의 경우의 수를 파악하는 문제

일반적으로 DP문제를 해결할때 Top-Down , Bottom-Up 방식을 이용한다고 인터넷을 떠돌아 다니면 배웠기 때문에

정확히는 모르겠지만 내가 푼 방식이 Bottom-Up이라 생각하고 풀어 보았다.

두 가지 방식을 통해 문제를 해결 하였는데

1. N이 1인 경우 부터 N까지의 경우의 수를 모두 파악하여 더해 주는 방법 (재귀 사용)

2. 특정값을 기준으로 전에 계산한 값을 통해 현재의 값을 구하는 방법(2중포문 배열 사용)

(제대로 설명을 못하는 것 같아 죄송합니다)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Arrays;

public class num_10844
{
    static public void main(String args[]) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());

        long[][] dp = new long[N+1][11]; // 계산한 값을 담아줄 배열을 만들어 준다.

        long result = 0; // 결과 값을 담아줄 변수

        for(int i=0; i<=10; i++)
        {
            dp[1][i] = 1;
        }

        for(int i=1;i<10;i++)
        {
             result += resolve(i,N,dp);
        }

//        resolve2(N,dp);
//            for (int j = 1; j < 10; j++)
//                result  += dp[N][j];


        System.out.print(result%1000000000);
    }

// 방법 1 재귀를 이용한 방법
    static long resolve(int index,int n, long[][] dp)
    {

        if (dp[n][index] > 0)
        {
            return dp[n][index]%1000000000;
        }
        if (n == 1) return dp[n][index] = 1;

        if (index == 0)
        {
            long temp = resolve(index + 1, n - 1, dp);
            dp[n][index] = temp;
        }
        else if(index == 9)
        {
            long temp = resolve(index - 1, n - 1, dp);
            dp[n][index] = temp;
        }
        else
        {
            long temp = (resolve(index - 1, n - 1, dp) + resolve(index + 1, n - 1, dp));
            dp[n][index] = temp;
        }

        return dp[n][index] %= 1000000000;

    }

    //내 현재위치를 기준으로 이전 단계에서 가질 수 있는 경우의 수를 파악한다.
   // 포문을 이용한 배열을 이용한 방법

    static long[][] resolve2(int n, long[][]dp)
    {
        for(int i=2; i<=n;i++)
        {
            for (int j = 0; j < 10; j++)
            {
                if(j == 0)
                {
                    dp[i][j]  = dp[i-1][j+1];
                }
                else if(j == 9)
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1];
                }

                dp[i][j] = dp[i][j] % 1000000000;
            }
        }
        return dp;
    }
}