백준 - 10844번, 쉬운 계단 수 (sol.java)

◎문제 링크

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

10844번: 쉬운 계단 수

---

◎문제 파악:

계단수: 모든 자리수의 차이가 1이 나는 수

목표: N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하기

 

1. 1 자리 수일 때: 1~9의 수는 모두 계단수이다. 

2. 2 자리 수일 때,

   0으로 시작하는 수는 1의 자리에 1을 붙일 수 있다. --> 01 (1 자리 수의 배열 index 1참조)

   1로 시작하는 수는 1의 자리에 0이나 2를 붙일 수 있다. --> 10,12 (1 자리 수의 배열 index 0,2 참조)

   2로 시작하는 수는 1의 자리에 1이나 3을 붙일 수 있다. -->  21,23 (1 자리 수의 배열 index 1,3 참조)

   ...

   9로 시작하는 수는 1의 자리에 8을 붙일 수 있다. --> 98 (1 자리 수의 배열 index 8 참조)

 

※ 0으로 시작하는 수는 없기 때문에 0을 고려하지 않는 것이 아니라,

그 다음 배열에서 1이 그 전 배열의 0을 사용하므로, 0까지 생각해주고 마지막에 종합할 때만 빼면 된다.

 

DP를 활용하여, 그 전 자리 수의 계단 수 배열을 참고하여 N자리 수의 계단수 배열을 만든다.

 

1의 자리 수 계단수

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1

 

10의 자리 수 계단수

0	1	2	3	4	5	6	7	8	9
1	2	2	2	2	2	2	2	2	1

 

100의 자리수 계단수

0	1	2	3	4	5	6	7	8	9
2	3	4	4	4	4	4	4	3	2

- 100의 자리수가 3일때 만들어질 수 있는 계단수의 개수는 4개이다.

---

◎코드 구현

package ProgrammersBj.Bj_NumberOfEasySteps;

import java.io.*;

public class MySolution {

	//목표 n번째 자리까지, 현재  now자리, arr: now-1번째 자리의 0~9로 시작하는 계단 숫자들의 개수
	public void solution(int n, int now, int[] arr) {
		
		//목표 자릿수에 도달하면, 1~9로 시작하는 값을 합침 (0으로 시작하는 숫자는 없으므로)
		if(n==now) {
			int answer=0;
			for(int i = 1; i<10;i++) {
				answer = (answer + arr[i])%1000000000;
			}
			System.out.print(answer);
			return;
		}
		
		//0~9로 시작하는 계단 숫자들의 개수를 위한 임시 배열
		int[] tmp = new int[10];
		
		for(int i = 0; i<10;i++) {
			//0으로 시작하면 그 전 수가 1이 될 수 밖에 없다
			if(i==0) {
				tmp[i] = arr[1];
				//9로 시작하면 그 전 수가 8이 될 수 밖에 없다
			}else if(i==9) {
				tmp[i] = arr[8];
				// 0이나 9가 아닌 , i로 시작하면, 그 전수가 i-1이나, i+1일 수 있다.
			}else {
				tmp[i] = (arr[i-1] + arr[i+1])%1000000000;
			}
		}
		// int의 범위 때문에 그리고 정답을 1,000,000,000으로 나눈 나머지를 출력하는것이기 때문에
		// %1000000000을 계산시마다 해준다.
		solution(n,now+1,tmp);
	}

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine());
		int[] arr = {1,1,1,1,1,1,1,1,1,1};
		MySolution sol = new MySolution();
		sol.solution(n,1,arr);
	}

}

 

실행 결과:

입력: 2
출력: 17

---

◎Github codes

https://github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/Bj_NumberOfEasySteps%2C21.05.28

jerry-ryu/java_problemsolving_algorithm