[PS] BOJ10844 쉬운 계단 수 ( DP ) With 파이썬, JAVA

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

10844번: 쉬운 계단 수

 

◎문제풀이

 

DP문제를 풀 때, 이차원 리스트를 발상이 어려워 문제풀이가 쉽지 않았다. 각 자리에는 0-9의 수가 들어갈 수 있다. ( 첫번째 자리에는 0이 들어갈 수 없다. ) 

 

 

 

 

8은 두 가지 경우로 생성된다. 

1) 7에서 +1 한 경우

2) 9에서 -1 한 경우

 

두 경우는 독립사건으로 경우의수는 합으로 구한다. 

 

d[8] = d[7] +d[9]

 

1-8까지는 이와 동일하지만 0과 9는 다르다. 

 

 

 

 

0과 9는 한 가지 경우에서 나온다. 

 

d[9] = d[8]

d[0] = d[1]

 

 

여기서 이전 자리와 현재 자리를 구분해야 하므로 이차원배열을 사용한다. 

 

d[n][8] = d[n-1][7] + d[n-1][9]

d[n][9] = d[n-1][8]

d[n][0] = d[n-1][1]

 

 

◎코드

 

파이썬

#BOJ10844 쉬운 계단 수

n = int(input())
d = [[0]*10 for _ in range(n+1) ]
d[1] = [0,1,1,1,1,1,1,1,1,1]


for i in range(2,n+1) :
  for j in range(10) :
    if j == 0 : d[i][j] = d[i-1][j+1] # 0인 경우
    elif j == 9 : d[i][j] = d[i-1][j-1] #9인 경우
    else : d[i][j] = d[i-1][j-1] + d[i-1][j+1] # 1-8인 경우

print(sum(d[n])%1000000000)

 

자바

import java.io.*;

public class Main{

    public static final int PIVOT = 1000000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n+1][10];

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

        for(int i=2;i<=n;i++){
            for(int j=0;j<=9;j++){
                if(j-1 >= 0) dp[i][j-1] = (dp[i][j-1] + dp[i-1][j])%PIVOT;
                if(j+1 <= 9) dp[i][j+1] = (dp[i][j+1] + dp[i-1][j])%PIVOT;
            }
        }

        long ans = 0;

        for(int i=0;i<=9;i++){
            ans += dp[n][i];
        }

        System.out.println(ans%PIVOT);
    }
}