[알고리즘][Java] 백준(BOJ) 10844 쉬운 계단 수_자바

 

DP

10844 쉬운 계단 수    https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• 이번 문제에서 중요한 부분은 정답을 1,000,000,000으로 나눈 나머지를 출력하는 것으로 해당 값들이 1,000,000,000 보다 큰 수일 수 있다는 부분이다. → int가 아닌 long으로 타입 지정해야 한다.
  • 타입 설정이 따로 필요없는 파이썬을 주로 사용했기 때문에 이 부분에서 실수가 있었다.(기초를 잡자.)
• 계단 수의 경우 n = 1 일 때는 1 - 9까지 모두 가능하다.
• n = 2 일 때는 1 뒤에는 0 또는 2가, 2 뒤에는 1 또는 3이, ..., 8 뒤에는 7 또는 9가, 9 뒤에는 8만 올 수 있다.
• 이런 규칙이 반복되는데 n = 3에서부터 나오는 0 뒤에는 1만 올 수 있다.
• 규칙을 만들면, 0 뒤에는 1만, 9 뒤에는 8만, 1 - 8 뒤에는 (해당 숫자 - 1) 또는 (해당 숫자 + 1)이 올 수 있다.
• 위의 규칙을 이용해서 개수를 세면 된다.
• dp에 초기값이 0인 2차원 배열을 저장한다.
  • dp [n+1][10]의 형태이다.
• 위의 규칙대로 이중 for문을 돌면서 개수를 저장한다.
  • 0 - 8 뒤(9가 아닐 때)에는 (해당 숫자 + 1)이 올 수 있다.
  • 1 - 9 뒤(0이 아닐 때)에는 (해당 숫자 - 1)이 올 수 있다.
• 마지막에 출력 전에는 반드시 1000000000으로 나눈 나머지를 출력하는 것을 잊지 않고 한다.

 

 

<코드>

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		
		long[][] dp = new long[n+1][10];
		int mod = 1000000000;
		for (int i=1; i<10; i++) {
			dp[1][i] = 1;
		}
		
		for (int i=2; i<=n; i++) {
			for (int j=0; j<10; j++) {
				if (j != 9) {
					dp[i][j+1] = (dp[i][j+1] + dp[i-1][j]) % mod;
				}
				if (j != 0) {
					dp[i][j-1] = (dp[i][j-1] + dp[i-1][j]) % mod;
				}
			}
		}
		
		long res = 0;
		for (int j=0; j<10; j++) {
			res += dp[n][j];
			res %= mod;
		}
		
		System.out.println(res);

	}

}

 

 

 

 

 

 

 

 

 

같은 문제 파이썬으로 푸는 방법

2021.01.13 - [Algorithm/백준 알고리즘_Python] - [알고리즘][Python] 백준(BOJ) 10844 쉬운 계단 수_파이썬

[알고리즘][Python] 백준(BOJ) 10844 쉬운 계단 수_파이썬