-
[java] 백준 알고리즘 10844번 쉬운 계단 수 풀이알고리즘/백준 알고리즘 2018. 5. 19. 10:34
이 문제는 이중배열을 사용해야 풀 수 있었다
이 문제를 푸는 가장 쉬운 방법은 이 문제는 이중배열을 사용해야 한다는 것과 4자릿수 정도까지 직접 써보면 된다.
4자릿수를 다 완성하기 전에 이미 규칙을 깨닫게 된다.
맨 앞자리가 1일 경우, 2번째 전 행의 앞자리 1인 계단 수 개수와 1번째 전 행의 앞자리가 2인 계단 수 개수를 합치면 된다.
맨 앞자리가 2~8은, 1행 전의 해당 열의 -1,+1열을 더한 값과 같다
맨 앞자리가 9는, 1행 전의 8열 계단 수와 같다.
** 한번 봅시다
맨 앞 자릿수
1
2
3
4
5
6
7
8
9
수의 길이: 1
1
(1)
1
(2)
1
(3)
1
(4)
1
(5)
1
(6)
1
(7)
1
(8)
1
(9)
수의 길이: 2
2
(10,12)
2
(21,23)
2
(32,34)
2
(43,45)
2
(54,56)
2
(65,67)
2
(76,78)
2
(87,89)
1
(98)
수의 길이: 3
3
(101,121,123)
4
(210,212,
232,234)
4
(321,323,
343,345)
4
(432,434,
454,456)
4
(543,545,
565,567)
4
(654,656,
676,678)
4
(765,767,
787,789)
3
(876,878,
898)
2
(987,989)
표에서 보듯이,
수의 길이가 늘어날수록, 직전 수의 길이 계단 수에 영향을 받는다
* 풀이소스
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647public class Baekjoon10844{public static void main(String[] args) throws NumberFormatException, IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));int n = Integer.parseInt(br.readLine());long[][] stairArray = new long[100][9]; // 최대 100행까지 생길 수 있음long result = 0;for(int i=0; i<9; i++) {stairArray[0][i] = 1; // 1행일 경우, 1~9까지 계단 수는 각각 1개다./* 2자리수 배열 */if(i==8) { // 9에 해당하는 계단수(0부터 시작하기 때문에 8이다)stairArray[1][i] = 1;}else {stairArray[1][i] = 2; // 9를 제외하고 2자리 수 계단 수는 2개씩있다.}}if(n>2) {for(int i=2; i<n; i++) { // 3행부터 즉, 3자리수부터 시작하는 이유는 맨 앞 1이 나올 경우, 2번째 전 행의 값을 활용하기 위해서for(int j=0; j<9; j++) {if(j==0) {stairArray[i][j] = (stairArray[i-2][j] + stairArray[i-1][j+1])%1000000000; // 앞자리 1의 경우, 2번째 전의 행 앞자리 1값 + 1개 행 전의 앞자리 2의 값}else if(j==8) {stairArray[i][j] = (stairArray[i-1][j-1])%1000000000; // 앞자리가 9의 경우, 1행 전의 앞자리가 8인 계단수들이다}else {stairArray[i][j] = (stairArray[i-1][j-1] + stairArray[i-1][j+1])%1000000000;}}}}for(int i=0; i<9; i++) {result += stairArray[n-1][i]; // 앞자리가 1~9인 계단수를 총 합치면 자릿수의 총 계단수가 나온다}bw.write(String.valueOf(result%1000000000));bw.flush();}}cs '알고리즘 > 백준 알고리즘' 카테고리의 다른 글
[java] 백준 알고리즘 10809번 알파벳 찾기 풀이 (0) 2018.05.19 [java] 백준 알고리즘 2577번 숫자의 개수 풀이 (0) 2018.05.19 [java] 백준 알고리즘 1065번 한수 풀이 (0) 2018.05.18 [java] 백준 알고리즘 10039번 평균점수 풀이 (0) 2018.05.18 [java] 백준 알고리즘 2920번 음계 풀이 (0) 2018.05.18