[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
- 문제
저번 문제인 1로 만들기보다 쉬운 편이다. 몇가지 규칙만 알면 되니 한 번 같이 알아보도록 하자.
- 알고리즘 [접근 방법]
문제를 설명하기 전에 자릿수 개념에 대해 헷갈려 하는 분들이 있어 먼저 한 번 정리하려고 한다. 그래야 필자가 설명하기도 편할 듯 하다.
N번째 자릿수라 하면 보통 길이가 N인 자연수에서 가장 왼쪽에 있는 수가 N번째 자리가 N번째가 된다. 만약 123456이라는 수가 있다고 하면 6번째 자릿수 자릿값은 1, 5번째 자릿수의 자릿값은 2, ⋯ , 첫번째 자릿수의 자릿값은 6이 된다.
소수의 경우 왼쪽에서 오른쪽으로 갈수록 자릿수가 증가하는 반면, 자연수는 그 반대다. 이 점 유의하면서 읽길 바란다. 그럼 문제로 돌아가보자.
문제 설명을 보면 일단 자릿수가 100, 즉 100째자리 수까지 주어지니 기본 형식은 long타입으로 해준다고 가정하고 설명하겠다.
또한 문제에서 가장 중요한 포인트는 '인접한 모든 자릿수가 1씩 차이가 난다'는 것이 포인트다.
여기서 유의해야 할 점이 있는데 다음 두 가지를 조심해야 한다.
1) N번째 자릿수의 자릿값이 0인 경우 : 다음 자릿수의 자릿값은 1밖에 올 수 없다.
2) N번째 자릿수의 자릿값이 9인 경우 : 다음 자릿수의 자릿값은 8밖에 올 수 없다.
즉, 10 다음에 붙을 수 있는 수는 1밖에 없으므로 101 이 되는 것이고, 만약 19가 온다면 8밖에 올 수 없으므로 198 이 되는 것이다. 그 외의 값(2~8)은 각 값보다 -1 또는 +1 인 값을 가질 수 있다.
그럼 자릿값은 0~9를 가질 수 있고, N개의 자릿값을 표현해야하므로 2차원 배열이 필요하다.
// N자릿수에 각각의 자릿값(0~9)를 의미
Long[] dp = new Long[N + 1][10]
자릿수는 배열의 경우 0부터 시작하기 때문에 N+1로 해주어 이해하기 쉽게 만들도록 하겠다.
알고리즘으로 탐색을 하는 방법은 크게 두 가지 방법이 있다. Top-Down 방식으로 재귀로 풀어내는 방법. Bottom-Up 방식으로 반복문으로 풀어내는 방법. 어떤 방식이던 크게 차이는 없지만 각 방법의 장단점은 존재한다. 이에 대한 것은 이전 포스팅인 '1로 만들기'를 보시길 바란다.
[Top-Down]
먼저 Top-Down방식으로 풀어보겠다. Top-Down방식의 장점은 역시 점화식을 그대로 적용할 수 있다는 점이다. 위에서 설명한 것처럼 우린 자릿수와 자릿값을 index로 쓸 2차원 배열을 필요로 한다. 그리고 재귀를 쓰기 위해 두 가지 변수를 둘 것인데, 자릿값을 표현 할 변수인 digit, 자릿값을 표현 할 변수인 val, 이렇게 두 개를 이용 할 것이다.
그리고 재귀호출은 자릿값에 따라 자릿값이 0이라면 다음에 올 자릿값은 1로, 9라면 8로 호출해주고, 그 외의 경우는 val-1, val+1 둘 다 가능하니 둘 다 호출하여 경우의 수를 합하면 된다.
글로 보면 이해하기 어려울 수 있으니 코드로 보면 이렇다.
/*
digit 는 자릿수, val은 자릿값을 의미함
첫째 자리수는 각 val이 끝이기 때문에
경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은
1로 초기화 되어있어야한다.
*/
static long recur(int digit, int val) {
// 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음
if(digit == 1) {
return dp[digit][val];
}
// 해당 자리수의 val값에 대해 탐색하지 않았을 경우
if(dp[digit][val] == null) {
// val이 0일경우 이전 자리는 1밖에 못옴
if(val == 0) {
dp[digit][val] = recur(digit - 1 ,1);
}
// val이 9일경우 이전은 8밖에 못옴
else if(val== 9) {
dp[digit][val] = recur(digit - 1, 8);
}
// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
else {
dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
}
}
return dp[digit][val];
}
위의 주석에서도 설명했지만 dp[1][0], dp[1][1], ⋯ ,dp[1][9] 는 1로 초기화 되어있어야 한다. 위 코드에서는 이 부분을 초기화 했다고 가정하고서 탐색 방법 위주로 코드를 보여주었다.
recur라는 함수를 탐색할 때, digit 번째 자릿수의 자릿값 val에 대하여 해당 자릿수의 경우의 수가 없는, 즉 dp[digit][val]이 null 인 경우 자릿값에 따라 3가지 경우로 나누어 digit-1번째 자릿수로 재귀호출을 해준다.
쉽게 말하면 N 번째 자릿수의 자릿값이 없으면 N-1번째 자릿수를 탐색하고, N-1 도 없으면 N-1의 -1 번째 자릿수를 탐색하여 값이 있을 때 까지 찾아나가는 방식인 것이다.
[Bottom-Up]
그렇다면 Bottom-Up 방식은 어떻게 할까? 위 코드를 정확하게 이해했다면 쉽게 반복문으로 옮길 수 있을 것이다. (적어도 필자는 재귀로 표현 가능 한 것 중 반복문으로 바꿀 수 없는 것은 아직까지 본 적 없다.)
Bottom-Up은 작은 문제들부터 풀어나가는 방식이니 다음과 같이 구성해주면 된다.
long[][] dp = new long[N + 1][10];
// 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개밖에 없음
for(int i = 1; i < 10; i++) {
dp[1][i] = 1;
}
// 두 번째 자릿수부터 N까지 탐색
for(int i = 2; i <= N; i++) {
// i번째 자릿수의 자릿값들을 탐색 (0~9)
for(int j = 0; j < 10; j++) {
// j=0, 즉 자릿값이 0이라면 이전 자릿수의 첫번째 자릿수만 가능
if(j == 0) {
dp[i][0] = dp[i - 1][1];
}
// j=9라면 이전 자릿수는 8만 가능
else if (j == 9) {
dp[i][9] = dp[i - 1][8];
}
// 그 외의 경우 이전 자릿수의 자릿값 +1, -1 의 합이 됨
else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]);
}
}
}
사실 엄연히 하면 자릿수가 거꾸로 되어있어 반대로 읽어야 하는데, 어차피 경우의 수를 구하는 것이기 때문에 크게 문제되진 않는다.
위 두가지를 토대로 풀어내면 된다.
- 4가지 방법을 사용하여 풀이한다.
두 알고리즘(Top-Down, Bottom-Up)에 대해 각 입력을 달리하여 성능을 비교해보고자 한다. 즉, 다음과 같이 네 가지 케이스로 나누겠다.
1 . Scanner + Top-Down
2. BufferedReader + Top-Down
3 . Scanner + Bottom-Up
4. BufferedReader + Bottom-Up
- 풀이
- 방법 1 : [Scanner + Top-Down]
import java.util.Scanner;
public class Main {
static Long[][] dp;
static int N;
final static long MOD = 1000000000;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
dp = new Long[N + 1][10];
// 첫번째 자릿수는 1로 초기화
for(int i = 0; i < 10; i++) {
dp[1][i] = 1L;
}
long result = 0;
// 마지막 자릿수인 1~9까지의 경우의 수를 모두 더해준다.
for(int i = 1; i <= 9; i++) {
result += recur(N, i);
}
System.out.println(result % MOD);
}
/*
dist 는 자릿수, val은 자릿값을 의미함
첫째 자리수는 각 val이 끝이기 때문에
경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은
1로 초기화 되어있어야한다.
*/
static long recur(int digit, int val) {
// 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음
if(digit == 1) {
return dp[digit][val];
}
// 해당 자리수의 val값에 대해 탐색하지 않았을 경우
if(dp[digit][val] == null) {
// val이 0일경우 이전 자리는 1밖에 못옴
if(val == 0) {
dp[digit][val] = recur(digit - 1 ,1);
}
// val이 1일경우 이전은 8밖에 못옴
else if(val== 9) {
dp[digit][val] = recur(digit - 1, 8);
}
// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
else {
dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
}
}
return dp[digit][val] % MOD;
}
}
가장 기본적인(?) 방법이라 할 수 있겠다.
참고로 MOD는 10억으로 초기화 되어있고, 분명히 문제에서 '10억으로 나눈 나머지 값'을 출력하라고 했다. N이 최대 100, 즉 자릿수만 100자리라 경우의 수일지라도 long타입을 벗어날 수 있다.(아니 벗어난다.) 때문에 long 범위에서 벗어나지 않도록 각 return마다 나머지값을 return시켜주어야 한다. 이 점만 유의하도록 하자.
- 방법 2 : [BufferedReader + Top-Down]
입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 입력 방법 빼고는 크게 달라진 것은 없다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static Long[][] dp;
static int N;
final static long MOD = 1000000000;
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];
// 첫번째 자릿수는 1로 초기화
for(int i = 0; i < 10; i++) {
dp[1][i] = 1L;
}
long result = 0;
// 마지막 자릿수인 1~9까지의 경우의 수를 모두 더해준다.
for(int i = 1; i <= 9; i++) {
result += recur(N, i);
}
System.out.println(result % MOD);
}
/*
dist 는 자릿수, val은 자릿값을 의미함
첫째 자리수는 각 val이 끝이기 때문에
경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은
1로 초기화 되어있어야한다.
*/
static long recur(int digit, int val) {
// 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음
if(digit == 1) {
return dp[digit][val];
}
// 해당 자리수의 val값에 대해 탐색하지 않았을 경우
if(dp[digit][val] == null) {
// val이 0일경우 이전 자리는 1밖에 못옴
if(val == 0) {
dp[digit][val] = recur(digit - 1 ,1);
}
// val이 1일경우 이전은 8밖에 못옴
else if(val== 9) {
dp[digit][val] = recur(digit - 1, 8);
}
// 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
else {
dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
}
}
return dp[digit][val] % MOD;
}
}
음.. 혹시 이해가 안될까 노심초사하니.. 만약 이해 안된다면 댓글 남겨주시길,,,
- 방법 3 : [Scanner + Bottom-Up]
이번에는 Top-Down방식이 아닌 Bottom-Up방식으로 반복문으로 풀어낸 방법이다.
import java.util.Scanner;
public class Main {
final static long mod = 1000000000;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
long[][] dp = new long[N + 1][10];
// 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개밖에 없음
for(int i = 1; i < 10; i++) {
dp[1][i] = 1;
}
// 두 번째 자릿수부터 N까지 탐색
for(int i = 2; i <= N; i++) {
// i번째 자릿수의 자릿값들을 탐색 (0~9)
for(int j = 0; j < 10; j++) {
// j=0, 즉 자릿값이 0이라면 이전 자릿수의 첫번째 자릿수만 가능
if(j == 0) {
dp[i][0] = dp[i - 1][1] % mod;
}
// j=9라면 이전 자릿수는 8만 가능
else if (j == 9) {
dp[i][9] = dp[i - 1][8] % mod;
}
// 그 외의 경우 이전 자릿수의 자릿값 +1, -1 의 합이 됨
else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
}
}
}
long result = 0;
// 각 자릿값마다의 경우의 수를 모두 더해준다.
for(int i = 0; i < 10; i++) {
result += dp[N][i];
}
System.out.println(result % mod);
}
}
크게 어려울 것은 없을 것이다. 오히려 이 방식으로 푼 사람이 더 많은 것 같다.
- 방법 4 : [BufferedReader + Bottom-Up]
마찬가지로 Bottom-Up방식에서 입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
final static long mod = 1000000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long[][] dp = new long[N + 1][10];
// 첫 번째 자릿수는 오른쪽 맨 끝의 자릿수이므로 경우의 수가 1개밖에 없음
for(int i = 1; i < 10; i++) {
dp[1][i] = 1;
}
// 두 번째 자릿수부터 N까지 탐색
for(int i = 2; i <= N; i++) {
// i번째 자릿수의 자릿값들을 탐색 (0~9)
for(int j = 0; j < 10; j++) {
// j=0, 즉 자릿값이 0이라면 이전 자릿수의 첫번째 자릿수만 가능
if(j == 0) {
dp[i][0] = dp[i - 1][1] % mod;
}
// j=9라면 이전 자릿수는 8만 가능
else if (j == 9) {
dp[i][9] = dp[i - 1][8] % mod;
}
// 그 외의 경우 이전 자릿수의 자릿값 +1, -1 의 합이 됨
else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
}
}
}
long result = 0;
// 각 자릿값마다의 경우의 수를 모두 더해준다.
for(int i = 0; i < 10; i++) {
result += dp[N][i];
}
System.out.println(result % mod);
}
}
- 성능
채점 번호 : 22145305 - 방법 4 : BufferedReader + Bottom-Up
채점 번호 : 22145298 - 방법 3 : Scanner + Bottom-Up
채점 번호 : 22145284 - 방법 2 : BufferedReader + Top-Down
채점 번호 : 22145278 - 방법 1 : Scanner + Top-Down
알고리즘의 큰 차이는 없는 듯 하다. 입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.
- 정리
생각보다 쉽게 풀 수 있는 문제였다. 필자의 경우 점화식을 구하면 그대로 재귀로 표현하면 되기 때문에 Top-Down방식을 선호하는 편인데, 아마 재귀에 익숙치 않은 분들이라면 조금 불편할 수도 있을 것 같다. 그래서 두 가지 방법 모두 올리긴 하는데, 본인이 편한 방식만 풀이하지 말고 다른 방법도 한 번 직접 구현해보는 것도 좋을 것 같다.
만약 이해가 안된다면 꼭 댓글 달아주시면 감사하겠다. 이 정도 문제까지 왔다면 대개 대부분은 이해 가겠지만, 혹여 필자가 설명을 어렵게 한다거나 그러한 부분이 있을까 항상 걱정이기 때문에... 적어도 많은 분들이 쉽게 이해할 수 있도록 노력하고자 하니 부탁드리겠다.
'JAVA - 백준 [BAEK JOON] > 동적 계획법 1' 카테고리의 다른 글
| [백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바] (17) | 2020.09.02 |
|---|---|
| [백준] 2156번 : 포도주 시식 - JAVA [자바] (21) | 2020.08.31 |
| [백준] 1463번 : 1로 만들기 - JAVA [자바] (35) | 2020.08.28 |
| [백준] 2579번 : 계단 오르기 - JAVA [자바] (35) | 2020.08.27 |
| [백준] 1932번 : 정수 삼각형 - JAVA [자바] (17) | 2020.08.26 |