[JAVA] BOJ(백준) - 쉬운 계단 수 - 10844

문제내용

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

10844번: 쉬운 계단 수

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

---

문제 접근 방법

문제가 너무 진짜 너무 어려웠다. 혼자서 풀다가 gg치고 다른 블로그들(https://st-lab.tistory.com/134 <--추천)을 참고 풀게됐다..

아니 처음에 점화식을 찾으려고 했는데 이게 점화식이 있어 ? 라는 생각부터 시작해서 별에별 생각을 다하다가 어쨋든 수의 조합이라 아닌걸 알지만서도 그냥 방문배열 없이 백트래킹처럼 풀어보려했는데 그것조차 쉽지 않았다..

 

결론적으로 점화식은 존재한다.

우선 dp배열을 'dp[길이][자릿값] = 경우의수' 로 정의해야한다. 이때 자릿값은 앞자리가 아니라 뒷자리부터 시작하는 수이다.

쉽게 말해보면

dp[2][0] 의 경우 길이가 2인 자리수일때 끝자리가 0이라면 앞에 올수 있는 수는 1

dp[2][1] 의 경우 길이가 2인 자리수일때 끝자리가 1이라면 앞에 올수 있는 수는 0,2

dp[2][2] 의 경우 길이가 2인 자리수일때 끝자리가 2라면 앞에 올수 있는 수는 1,3

...

dp[2][9] 의 경우 길이가 2인 자리수일때 끝자리가 9라면 앞에 올수 있는 수는 8

 

자릿값이 0, 9일때는 바로앞 자리로 1, 8만 올수 있고

자릿값이 1~8일때는 바로앞 자리로 -1, +1한 값이 올수 있다.

 

즉,

0일 경우 dp[길이][자릿값] = dp[길이-1][1]

9일 경우 dp[길이][자릿값] = dp[길이-1][8]

1~8일 경우 dp[길이][자릿값] = dp[길이-1][자릿값-1] + dp[길이-1][자릿값+1]

로 점화식을 만들 수 있다.

 

이를 활용하면 문제를 풀 수 있다.

 

---

풀이

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

public class BOJ_10844 {
	static int[][] dp; //dp[길이][자릿값]
	static int mod = 1000000000;//문제에서 나누라고 주어진 수
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		dp = new int[n+1][10];//0번인덱스는 사용안할꺼라서 n+1로.
		
		for(int i=0; i<10; i++) {//초기화
			dp[1][i] = 1;
		}
		
		long result = 0;
		//길이가 n이면서 끝자리가 1~9일때 모든 경우의수를 합한다.
		for(int i=1; i<10; i++) {
			result += stairNum(n,i);
		}
		
		System.out.println(result%mod);
	}
	
	public static int stairNum(int length, int num) {
		//맨뒤에서 앞자리로 하나씩 오면서 맨앞자리로 왔을때 반환
		if(length==1) {
			return dp[length][num];
		}
		
		//아직 계산 안한건 아래의 경우로 계산
		if(dp[length][num]==0) {
			if(num==0) {//입력되는 끝자리가 0일때 앞에 1만 올수 있다.
				dp[length][num] = stairNum(length-1,1);
			}else if(num==9) {//입력되는 끝자리가 9일때 앞에 8만 올수 있다.
				dp[length][num] = stairNum(length-1,8);
			}else {//그외의 경우는 +1, -1 한 값이 올수 있다.
				dp[length][num] = stairNum(length-1,num-1) + stairNum(length-1,num+1);
			}
		}
		
		//단위가 정수형 범위 넘어가서 return값 마다 나머지를 반환
		return dp[length][num]%mod;
	}
}

 

---

마치며

이번문제 제목은 쉬웠지만 내용은 쉽지않은 문제였다..

특히 이번 문제의 경우 이전 문제처럼 값을 합치거나 빼서 값을 누적시키는게 아니라

값의 조합을 누적시켜야하고 조합할수 있는 규칙을 찾아서 식을 세우는게 매우 어렵웠고 현타가 좀 온 문제이다..

그래도 포기하지말고 꾸준히 하면 될꺼라 믿는다.