백준 [자바 java] 백준 10844 : 쉬운 계단 수

 

처음 이 문제를 봤을 때는 무슨 말인지 이해가 잘 되지 않아서 여러번 읽어봤다. 한마디로 n자리수들 중에서 인접한 수의 차이가 모두 1인 수들의 갯수를 구하라는 문제이다. 

예를 들어 n이 2일 때 10,12,21,23,32,34...이런 수들이 있고 이들의 개수를 출력해야 하므로 출력 값은 17이다.

 

처음에는 수학적 공식(?)이 dp보다 훨씬 간편할 것이라고 생각했지만 그건 나의 착각이었다. 앞에는 쫌 잘 돌아갔지만 25까지만 돌아가고 뒤에는 거의 안 돌아갔다. 당연히 시간 초과가 났고 이런저런 약간의 조치를 취했지만 해결되지는 않았다ㅜ

 결국 다 지우고 dp로 해결해보았다. 2차원 배열을 만든 후 세로축은 0부터 9 그리고 가로 축은 자릿수를 의미한다. 

일의 자릿 수에서 끝이니까 dp[i][1]은 다 1을 넣어주었고(반복문 쓰면 훨씬 편했을텐데..ㅋ)  반복문을 이용해서 각 칸을 채워 넣었다.

 

실수 1. 바깥쪽 for문에 자릿수를 의미하는 수를 넣고 자릿수 별로 0-9를 채워 넣어야 하는데 반대로 해서 틀렸다. 

실수 2. 안쪽 for문에 0을 포함시키지 않았다.

실수 3. 10억으로 나눈 나머지를 출력하라고 해서 끝에만 나누게 했는데 앞에서도 int의 범위를 넘어가는 경우가 있어서 마이너스 어쩌고 이런 식으로 출력이 되어 답이 이상하게 나왔다. 

import java.io.*;
import java.util.*;



class Main {
	
	public static void main(String[] arg) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
		Stack<Integer> stack1 = new Stack<>();
		Stack<Integer> stack2 = new Stack<>();
		
		
		
		int n = Integer.parseInt(br.readLine());
		
		int i,j;
		int[][] dp = new int[10][n+1];
		int cnt = 0;
		
		
		dp[0][1] = 1;
		dp[1][1] = 1;
		dp[2][1] = 1;
		dp[3][1] = 1;
		dp[4][1] = 1;
		dp[5][1] = 1;
		dp[6][1] = 1;
		dp[7][1] = 1;
		dp[8][1] = 1;
		dp[9][1] = 1;
		
		 for(j = 2;j<=n;j++){
			 for(i =0 ;i<=9;i++){
				if(i == 0) {
					dp[i][j] = dp[i+1][j-1];
				}
				else if(i == 9) {
					dp[i][j] = dp[i-1][j-1];
				}
				else {
					dp[i][j] = (dp[i-1][j-1]+ dp[i+1][j-1])%1000000000;
				}
				
			}
 
		}
		 
		 for(i = 1;i<=9;i++) {
			 cnt+=dp[i][n];
			cnt%=1000000000;
		 }
		System.out.println(cnt);
		 
			
		 
	
		
}

}

기억해야 할 것

1. 시간 초과가 날 수 있으니까 제출 전에 가장 큰 수 넣어보기

2. ~으로 나눈 나머지를 출력하라고 하면 더하는 과정에서도 계속 나눈 나머지를 더해주기

3. 바깥쪽 for문이랑 안쪽 for문 중 어떤 것이 어디로 가야 할지 신중하게 고르기

 

다른 사람의 코드와 다른 점

딱히 없었따!