[문제] 백준 10844번 쉬운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

풀이

DP 는 어렵지 않게 풀었지만, mod연산때문에 계속 틀렸었다.

sum += dp[N][i] % mod; 에서 연산자 우선순위를 고려해야한다.

 

public class BOJ_10844 {
	static long mod = 1000000000;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
	
		long[][] dp = new long[N+1][10];
		dp[1][0] =0;
		for(int i=1;i<=9;i++) {
			dp[1][i] = 1;	
		}
		if(N==1) {
			System.out.println(9);
			return;
		}
		
		// i 자리수에서 마지막 자리수가 j인 것 찾기
		for(int i=2;i<=N;i++) {
			dp[i][0] = dp[i-1][1]%mod;
			for(int j=1;j<9;j++) {
				dp[i][j] = (dp[i-1][j+1]+ dp[i-1][j-1])%mod;
			}
			dp[i][9] = dp[i-1][8]%mod;
		}
		long sum = 0;
		for(int i=0;i<10;i++) {
			sum = (sum+ dp[N][i])%mod;
		}
		System.out.println(sum);
	}

}