생각정리/코딩테스트
[JAVA 알고리즘]BAEKJOON 10844번 쉬운 계단 수
생각중임
2023. 12. 19. 22:48
다이나믹 프로그래밍을 이용해서 문제를 해결하는 문제
쉬운 계단 수
문제 설명
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
제한사항
- 없음
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
입출력 예
| input | return |
| 1 | 9 |
| 2 | 17 |
나의 문제풀이
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bufferedReader.readLine());
bufferedReader.close();
int[][] stairs = new int[N + 1][10];
// 0으로 시작하는 수는 계단수가 아니다.
for(int i = 1; i <= 9; i++) {
stairs[1][i] = 1;
}
for(int i = 2; i <= N; i++) {
for(int j = 0; j <= 9; j++) {
// 0은 1일 경우에만 나올 수 있다.
if(j == 0) {
stairs[i][0] = stairs[i - 1][1] % 1000000000;
}
// 9는 8일 경우에만 나올 수 있다.
else if (j == 9) {
stairs[i][9] = stairs[i - 1][8] % 1000000000;
}
// 그 외의 경우 이전 자릿수의 양쪽의 값을 더한다.
else {
stairs[i][j] = (stairs[i - 1][j - 1] + stairs[i - 1][j + 1]) % 1000000000;
}
}
}
long answer = 0;
for(int i = 0; i <= 9; i++) {
answer += stairs[N][i];
}
System.out.println(answer % 1000000000);
}
}- 0으로 시작하는 수는 계단수가 아니기 때문에 0을 제외한 한 자릿수를 1로 정의해준다.
- 두 자릿수부터 입력수 까지반복을 하면서 0~9의 수를 반복한다.
- 0일 경우, 1일 경우에만 계단수가 성립하기 때문에 전 자릿수의 1의 개수를 입력한다.
- 9일 경우, 8일 경우에만 계단수가 성립하기 때문에 전 자릿수의 8의 갯수를 입력한다.
- 그 외의 경우, 전 자릿수의 자신 보다 1 큰 수와 작은 수를 더한 갯수를 입력한다.
- 각 수를 입력할 때 값이 int의 크기를 벗어나지 않도록 1000000000으로 나눠준다.
- 주어진 N 자릿수의 모든 수를 더해준다. (int의 크기를 벗어날 수 있으므로 long으로 선언해 준다.)
타뷸레이션 방식을 이용해 아래의 값부터 만들어 원하는 값까지를 구해 답을 찾아내는 방법을 선택했다.
문제의 주어진 내용을 봤을 때 0으로 시작하는 수는 계단수가 아니다에서 한 자릿수의 경우 0을 제외한 수들은 다 1개씩이 있고, 두 자릿수를 예를 들어 봤을 때 9를 제외한 나머지 수들은 다 자신보다 큰 수와 작은 수로 나눠질 수 있었다. 이를 봤을 때 0과 9일 경우는 나눠 질 수 없고 하나의 경우의 수만 나오도록 생각을 했었는데, 이렇게 생각을 하면 언제 0과 9가 오는지 알 수가 없어 역으로 생각을 해서 0과 9일경우는 언제 생기는 지를 보면 1과 8일 경우에만 나올 수 가 있어 해당 규칙을 이용해서 반복문을 구현했다.
그리고 출력에서 1000000000으로 나눈 나머지를 출력한다는 건 해당 값이 일정 이상으로 올라갈 수 있다는 뜻일 수 있어 자료형을 사용하는데 잘 고려해야 된다.