DP #10844: 쉬운 계단 수 [JAVA]

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

 

10844번: 쉬운 계단 수

 

 

---

 

 

 

문제 접근

 

 

 

 

 

계단수이기 때문에 기본적으로 둘째 자리 숫자는 첫째 자리 숫자의 -1 또는 +1한 수가 나타난다.

 

 

다만, 예외가 있는데 첫째 자리 숫자가 9인 경우는 둘째 자리에 8만 올 수 있고

 

N=3이상이고 첫째 자리 숫자가 1인 경우, 둘째 자리 숫자는 0이 올 수 있는데 그럼 셋째 자리 숫자는 반드시 1이 와야한다.

 

 

 

 

 

 

이러한 예외를 염두하여 관계식을 작성하면 다음과 같다.

 

 

 

 

 

dp[N][i]는 N자리수이고 첫째 자리 수가 i일 때 계단 수의 개수

 

 

 

 

 

 

코드

 

 

 

top down - 재귀

 

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


public class Main {
	
	static Long[][] dp;
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(bf.readLine());
		
		dp=new Long[101][10];
		
		for(int i=1;i<=9;i++) {
			dp[1][i]=1L;
			dp[2][i]=2L;
		}
		dp[2][9]=1L;
		
		 
		long sum=0;
		for(int i=1;i<=9;i++) {
			sum+=recur(N,i);
		}
		
		
		System.out.println(sum%1000000000);
		
		
		bf.close();
	}
	
	static long recur(int N, int i) {
		
		if(dp[N][i]==null) {
			if(i==1) {
				dp[N][1]=recur(N-2,1)+recur(N-1,2);
			}
			else if(i==9) {
				dp[N][9]=recur(N-1,8);
			}
			else {
				dp[N][i]=recur(N-1,i-1)+recur(N-1,i+1);
			}
		}
		
		
		return dp[N][i]%1000000000;
	}
	
}

 

 

 

 

 

bottom up - 반복문

 

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


public class Main {
	
	static Long[][] dp;
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(bf.readLine());
		
		dp=new Long[101][10];
		
		for(int i=1;i<=9;i++) {
			dp[1][i]=1L;
			dp[2][i]=2L;
		}
		dp[2][9]=1L;
		
		for(int j=3;j<=N;j++) {
		
			for(int i=1;i<=9;i++) {
				if(i==1) {
					dp[j][1]=(dp[j-2][1]+dp[j-1][2])%1000000000;
				}
				else if(i==9) {
					dp[j][9]=dp[j-1][8]%1000000000;
				}
				else {
					dp[j][i]=(dp[j-1][i-1]+dp[j-1][i+1])%1000000000;
				}
			}
		}
		
		long sum=0;
		
		for(int i=1;i<=9;i++) {
			sum+=dp[N][i];
		}
		
		System.out.println(sum%1000000000);
		
		bf.close();
	}
	
	
}

 

 

 

 

 

 

 

 

▲ 참고 및 주의사항

 

 

1. N이 최대 100까지 가능하므로 즉, 100자리 수가 올 수 있으므로 long 타입을 써야한다.

 

 

2. 모듈러 연산 관련

 

https://st-lab.tistory.com/19

(A+B) %C = (A%C + B%C)%C 

(A*B)%C = (A%C * B%C)%C 

 

 

3. 좀 더 깔끔한 풀이

https://st-lab.tistory.com/134