[백준]동적 계획법1/쉬운 계단 수/10844 풀이 JAVA

문제

45656이란 수를 보자.

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

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

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

 

입력

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

 

출력

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

 

 

풀이(JAVA)

dp[N][index] = m이라고 할 때, 이는 N번째 자리가 index일 때 계단의 수가 m개임을 뜻한다.

예를 들면 dp[3][5] = 4;는

3의 자리가(100의 자리) 5일 때 계단의 수는 543, 545, 567, 565로 4개라는 뜻이다.

(※2의 자리는 10의 자리, 4의 자리는 1000의 자리이다.)

 

아래 표를 보며 문제를 이해해보자.

 

N = 1일 때 계단의 수 = 9

dp[1][0~9] = 9; 

N/index	0	1	2	3	...	6	7	8	9
1	1	1	1	1	1	1	1	1	1

1계단

0

1

2

3

...

6

7

8

9

 

N = 2일 때 계단의 수 = 17

dp[2][0~9] = 17;

N/index	0	1	2	3	...	6	7	8	9
1	1	1	1	1	1	1	1	1	1
1 계단	0	1	2	3	...	6	7	8	9
2	1	2	2	2	2	2	2	2	1
2 계단	01	10, 12	21, 23	32, 34	...	65, 67	76, 78	87, 89	98

(dp[2][0] = 1의 01에서 파란 부분은 인덱스, 빨간 부분은 dp[1][1]의 계단, 마찬가지로

dp[2][1] = 2의 10, 12에서 파란 부분은 인덱스, 빨간 부분은 dp[1][0]과 dp[1][2]의 계단...)

 

N = 3일 때 계단의 수 = 32

dp[3][0~9] = 32;

(앞에 생략된 부분은 위와 같음)

N/index	0	1	2	3	...	6	7	8	9
2계단	01	10, 12	21, 23	32, 34	...	65, 67	76, 78	87, 89	98
3	2	3	4	4	...	4	4	3	2
3계단	010, 012	101, 121, 123	210, 212, 232, 234	321, 323, 343, 345	...	654, 656. 676. 678	765, 767, 787, 789	876, 878, 898	987. 989

(dp[3][0] = 2의 010, 012에서 초록 부분은 인덱스, 파란 부분은 dp[2][1]의 계단, 마찬가지로

dp[3][1] = 3의 101, 121, 123에서 초록 부분은 인덱스, 파란 부분은 dp[2][0]과 dp[2][2]의 계단,

dp[3][2] = 4의 210, 212, 232, 234에서 초록 부분은 인덱스, 파란 부분은 dp[2][1]과 dp[1][3]의 계단...)

 

표를 잘 이해했다면 점화식도 쉽게 알 수 있다.

dp[N][index] = dp[N - 1][index - 1] + dp[N - 1][index + 1]이다.

 

이때 주의해야 할 점은,

index가 0일 때는 index - 1에서 -1,  index가 9일 때 index + 1에서 10이라 인덱스 에러가 난다.

이는 0다음에 -1이 아닌 1만 올 수 있음과 9 다음에 10이 아닌 8만 올수 있음을 나타낸다.

이 부분의 예외를 잘 표현해주면 아래 코드와 같이 나타낼 수 있다.

 

 

	import java.io.*;
	public class Main {
	static long[][] dp; // 계단 수를 저장할 배열
	// ex) dp[N][index] = m; N의 자리수가 index일 때 계단 수 m개
	// ex) dp[2][3] = 2; 2의 자리수가 3인 계단 수는 2개(32, 34)
	static long find(int N, int index) {
	if (N == 1) return dp[N][index]; // 1의 자리수는 1 리턴
	if (dp[N][index] == 0) // dp[N][index]가 정의되어있지 않으면
	if (index == 0) // N의 자리 수가 0이면 다음에 올 수는 반드시 1
	dp[N][index] = find(N - 1, 1);
	else if (index == 9)// N의 자리 수가 9면 다음에 올 수는 반즈시 8
	dp[N][index] = find(N - 1, 8);
	else // N의 자리 수가 index이면 다음에 올 수는 1 작거나 1 큰 수
	dp[N][index] = find(N - 1, index - 1) + find(N - 1, index + 1);
	// 출력 조건 : 1,000,000,000으로 나눈 나머지
	return dp[N][index] % 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 long[N + 1][10]; // 설명 편하게 하기 위해 N + 1로 선언(dp[0]은 안 씀)
	for (int index = 0; index < 10; index++)
	dp[1][index] = 1L;
	long result = 0; // 계단 수 결과
	for (int index = 1; index < 10; index++) // 0으로 시작하는 계딴은 없으니 1부터 계단수 세기
	result += find(N, index); // N의 자리가 index인 계단 수를 누적하여 저장
	// 출력 조건 : 1,000,000,000으로 나눈 나머지
	System.out.println(result % 1000000000);
	}
	}

view raw 10844-1.java hosted with ❤ by GitHub

 

(dp배열을 dp[N + 1][10]이 아니라 dp[N][index]로 만든 풀이)

	import java.io.*;
	public class Main {
	static long[][] dp;
	static long find(int N, int index) {
	if (N == 0) return dp[N][index];
	if (dp[N][index] == 0)
	if (index == 0)
	dp[N][index] = find(N - 1, 1);
	else if (index == 9)
	dp[N][index] = find(N - 1, 8);
	else
	dp[N][index] = find(N - 1, index - 1) + find(N - 1, index + 1);
	return dp[N][index] % 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 long[N][10];
	for (int index = 0; index < 10; index++)
	dp[0][index] = 1L;
	long result = 0;
	for (int index = 1; index < 10; index++)
	result += find(N - 1, index);
	System.out.println(result % 1000000000);
	}
	}

view raw 10844-2.java hosted with ❤ by GitHub

---

한 번 이해하고 나니 코드가 쉽게 짜지는.... 거 같기도!?