[백준][java] 쉬운 계단 수 10844번

점화식 구하기

점화식은

i가 홀수일 경우: d[i] = (d[i-1]-2)*2+2

i가 짝수일 경우: d[i]=(d[i-1]-1)*2+1

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

public class 쉬운계단수10844 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long[] d = new long[n+1];
		d[0] = 0;
		d[1] = 9;
		for(int i = 2; i<d.length; i++) {
			if(i%2==0) {
				d[i] = ((d[i-1]-1)*2+1)%1000000000;
			}else {
				d[i] = ((d[i-1]-2)*2+2)%1000000000;
			}
		}
		System.out.println(d[n]%1000000000);
	}
}

라고 생각했지만… 틀렸다.

Top-down방식

구글링을 통해 점화식을 이차원 배열을 만들어 사용하는 것을 알게 되었다.

1차 배열은 자릿수, 2차 배열은 자리값(개수)가 저장되는 이차원 배열 dp를 선언하고 rcur이라는 재귀함수로 input값 n자리부터 0자리까지 탐색하여 배열을 채우는 방식으로 구현하는 방식이다.

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

public class 쉬운계단수10844 {
	static Long[][] dp;
	static int N;
	final static long MOD = 1000000000;
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		N = in.nextInt();
		dp = new Long[N + 1][10];
		
		// 첫번째 자릿수는 1로 초기화 
		for(int i = 0; i < 10; i++) {
			dp[1][i] = 1L;
		}
		
		long result = 0;
		
		// 마지막 자릿수인 1~9까지의 경우의 수를 모두 더해준다.
		for(int i = 1; i <= 9; i++) {
			result += recur(N, i);
		}
		System.out.println(result % MOD);
	}
	
	/*
	 dist 는 자릿수, val은 자릿값을 의미함
	 
	 첫째 자리수는 각 val이 끝이기 때문에
	 경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은
	 1로 초기화 되어있어야한다.
	*/
	
	static long recur(int digit, int val) {		
 
		// 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음
		if(digit == 1) {
			return dp[digit][val];
		}
			
		// 해당 자리수의 val값에 대해 탐색하지 않았을 경우 
		if(dp[digit][val] == null) {
			// val이 0일경우 다음은 1밖에 못옴
			if(val == 0) {
				dp[digit][val] = recur(digit - 1 ,1);
			}
			// val이 1일경우 다음은 8밖에 못옴
			else if(val== 9) {
				dp[digit][val] = recur(digit - 1, 8);
			}
			// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
			else {
				dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
			}
		}
		return dp[digit][val] % MOD;
	}
}

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