[백준][DP][10844] 쉬운 계단 수

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

- 소스코드

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
		
	int n = sc.nextInt();
	long[][] dp = new int[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] += dp[i-1][j-1];
			}
			if(j+1 <= 9){
				dp[i][j] += dp[i-1][j+1];
			}
		
			dp[i][j] %= 1000000000;
		}
	}
		
	long ans = 0;
	for(int i=0; i<=9; i++){
		ans += dp[n][i];
	}
	
	ans %= 1000000000;
		
	System.out.println(ans);
}

- Category : 다이나믹 프로그래밍

- My Thinking

처음에 logic이 아무리 생각해도 맞다고 생각했는데 결과가 틀렸다고 계속해서 나왔다. 그래서 이유를 찾아보니 계속해서 생각해보니, 결과값을 10억으로 나누는 부분에서 힌트를 찾게 되었다. JAVA에서 int의 최대범위는 21억인데 결과를 더하거나 하다보면 int의 범위를 초과하게 된다. 그래서 5번째라인의 dp변수와 24번째 라인의 dp변수를 long타입으로 변경해서 이 문제를 해결할 수 있다. 여기서 중간에 for문을 돌면서 10억을 계속해서 나누는 이유는 더하면서 중간 값이 int를 초과할 수 있기 때문에 중간에 계속해서 10억을 나눠야한다.

- Logic

2차원 다이나믹 프로그래밍을 이용해야 한다. 메모이제이션을 하기 위해 dp[자리 수][마지막 수] 변수를 선언한다.  문제에서 0은 초기화하지 않는다라는 조건이 붙어있기 때문에, 0을 제외한 길이가 1인 1~9를 초기화한 후 진행한다. 여기서 주의해야할 점은 끝이 0과 9일 때이다. 끝이 0일 경우에는 이전 값이 -1은 될 수 없기 때문에 무조건 1밖에 올 수 없다. 마찬가지로 9일 경우에도 이전 값이 10이 될 수는 없기 때문에 무조건 8이 와야한다. 나머지 1~8에서는 이전 값이 -1과 +1 둘 다 올 수 있기 때문에 이를 if문을 이용해서 문제를 해결했다.