[백준][JAVA알고리즘]10844번 풀이(쉬운 계단 수) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 10844번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 10844 (쉬운 계단 수)

문제

45656이란 수를 보자.

 

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

 

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

 

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

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

출력

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

제한

시간제한 : 1 초 (추가 시간 없음)

입력 예시

1

출력 예시

9

입력 예시

2

출력 예시

17

성공코드

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

public class Main {

	static int N ;
	static long[][] dp;
	static long sum = 0;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		dp=new long[N+1][10];
		
		for(int i = 0 ; i < 10 ; i++)
			dp[1][i]=(long) 1;
		
		for(int i = 1 ; i < 10 ; i++) 
			sum += stair(N,i);
			
		System.out.println(sum%1000000000);

}
	public static long stair(int digit, int val) {
		
		if(digit == 1)
			return dp[digit][val];
		
		if(dp[digit][val] == 0) {
		if(val==0) 
			dp[digit][val] = stair(digit-1,val+1);
		else if(val ==9)
			dp[digit][val] = stair(digit-1,val-1);
		else
			dp[digit][val] = stair(digit-1,val-1) + stair(digit-1,val+1);
		}
		
		return dp[digit][val]%1000000000;
	}
}

네.... 이번 알고리즘은 저에게 정말 힘들었습니다..... 결국 제 한 시간 안에 다 풀지 못하여 다른 사람의 코드를 참고해서 해설을 풀어드립니다. 해당 사항은 우선 점화식을 어떻게 세워야 할지가 가장 막막했습니다.

 

자 STEP을 따라가며 천천히 이해를 같이 해보도록 하죠.

---

알고리즘 흐름도

입력받기 -> 초기화 해주기 -> 반복하여 값 넣어주기 -> 재귀 구현하기 -> 출력하기

---

STEP1 문제 이해하기 및 점화식 세워보기

 우선 구현을 하기전에 문제를 이해하고 어떠한 방법으로 구현할지 고민해야 합니다!

이걸 구현하면서 대표적인 방법으로 Bottom-up / Top-down방식이 있다고 합니다. 간단히 말하면 아래부터 찾느냐 위에서부터 찾느냐의 차이점입니다. 뭐 각자가 편하신 방법으로 하시면 된다고 생각합니다~

 

자 이제 잘 생각해보면, 45656이란 수를 보면 인접한 모든 자릿수 차이가 1이 난다. 이러한 계단을 쉬운 계단 수라 고하는데 가짓수를 구하는 문제입니다. 

 

해당 문제를 풀기위해서 점화식을 잘 세워야 쉽게 풀이할 수 있습니다. 대부분의 DP문제가 점화식을 기반으로 풀게 되죠. 한 번에 점화식이 도출이 안된다면, 나열하여 점화식을 세우면 됩니다. 이때 앞서 말한 것처럼 가짓수에 중점을 두고 생각을 해야 합니다. 가보도록 하죠. (지금 하는 방식은 TOP-DOWN방식입니다.)

 

N=0

N=1

1 2 3 4 5 6 7 8 9

N=1일때	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1(일의자리)	0	1	1	1	1	1	1	1	1	1

 

N=2

10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98

N=2일때	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1(일의자리)	1	1	1	1	1	1	1	1	1	1
2(십의 자리)	0	2	2	2	2	2	2	2	2	1

 

N=3

101 121 123 ......

N=3일때	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1(일의자리)	1	1	1	1	1	1	1	1	1	1
2(십의 자리)	1	2	2	2	2	2	2	2	2	1
3(백의 자리)	0	3	4	4	4	4	4	4	3	2

네... 여기까지만 하셔도, 충분히 나열했습니다. 이제는 규칙을 찾아봐야 합니다. 물론 n이 0, 1일 때는 보이지가 않습니다. 그렇다면 2와 3일 때를 봐야 합니다. 저희가 결국에 원하는 값은 마지막, 십의 자리 또는 백의 자리에 있는 가짓수를 더하면, 원하는 결과가 나오는 것을 알 수 있습니다. (왜 그런지는 정확히 알지 못하겠습니다. 단, 문제에서 가지 수를 찾고 있음으로 그에 맞게 각 숫자가 나올 수 있는 가짓수로 추론해 볼 수 있었습니다.)

 

규칙이 바로 보이지 않으시는 분도 있으니 하나씩 알려드리겠습니다. 결국 저희가 구하려는 값에서 (n=3일 때) 0이 백의 자리에 나올 경우의 수는 0이 됩니다. 왜냐하면, 문제에서 나왔듯이 0이 맨 앞에 올 수 없기 때문이죠

 

1의 경우의 수는 3입니다. 이는 자기 자신을 제외한 0(십의 자리)과 2(십의 자리)를 더한 숫자가 되죠. 이런 식으로 모든 수들은 Y자 형태로 값이 도출이 됩니다. 자기 자신보다 1이 크거나 작은 값의 가짓수를 더한 값이 됩니다. 

이를 기억하시면 좀 더 쉽게 풀이할 수 있죠. 다음 STEP으로 넘어가 봅시다.

 

---

STEP2 초기화해주기

		dp=new long[N+1][10];
		
		for(int i = 0 ; i < 10 ; i++)
			dp[1][i]=(long) 1;

dp를 long배열로 [N+1][10]으로 선언해 줍니다. (행은 입력으로 받은 N을 가리키고 열은 0 ~ 9의 숫자를 의미합니다.)

 

그다음 가장 처음의 숫자를 1로 초기화해줍니다. (앞서 살펴본 일의 자리입니다.)  이건 뭐... 일의 자리를 초기화해주려고 하는 겁니다.

 

(그렇다면, 만약에 N=1일 때 0은 0이어야 되는 거 아닌가?라는 의문이 있겠지만, 이것은 합에서 빼주면 됩니다. 아래처럼 말이죠)

		for(int i = 1 ; i < 10 ; i++) 
			sum += stair(N,i);

인덱스 시작을 1부터 하면 됩니다. 몇 자리가 되든 0번째 값은 더하지 않기 때문에 상관이 없게 되죠.

 

---

STEP 3 재귀 구현하기

핵심입니다.

	public static long stair(int digit, int val) {
		
		if(digit == 1)
			return dp[digit][val];
		
		if(dp[digit][val] == 0) {
		if(val==0) 
			dp[digit][val] = stair(digit-1,val+1);
		else if(val ==9)
			dp[digit][val] = stair(digit-1,val-1);
		else
			dp[digit][val] = stair(digit-1,val-1) + stair(digit-1,val+1);
		}
		
		return dp[digit][val]%1000000000;
	}

가장 먼저 해줄 것은 IF문으로 digit 즉 자릿수가 1이라면 그냥 해당 값을 return 해 줍니다.

 

두 번째 if문의 의미는 바로 재귀를 돌리자 않았다면 입니다.해당 값이 0이라면, 바로 재귀를 하면되는 것이죠.

두번째 if문안에 있는 3가지를 간략히 알려드리면

 

if -> 0이 들어가는 가짓수를 셀 때는 오른쪽 위에 있는 곳을 가리켜야 합니다.

else if -> 9가 들어가는 가지수를 셀때는 왼쪽 위에 있는 곳을 가르켜야 합니다.

else -> 나머지 숫자들은 왼쪽 위, 오른쪽 위를 더해서 가리켜야 합니다.

 

해당처럼 dp에 재귀를 통한 값을 넣어주면 결국 n=3이라고 가정한다면 1행 까지 내려가면서 1이 더해지게 되죠. 결론적으로 앞서 살펴본 sum에는 마지막 백의 자리에 이는 값들이 다 더해져 답으로 나오게 됩니다.

 

반환 값에 % 은 문제에 제시되어있습니다.

---

... 설명이 많이 부족해 보이지만,.... 재귀는 뭐 많이 사용되고 이해하기가 어렵지만 결론적으로는 많이 풀어보셔야 합니다. 어렵다고 재껴두지 마시고 하나씩 풀어보고 모르면 베껴보고, 그 후에 이해하셔도 충분히 공부가 되실 겁니다.