[BOJ] 백준 2688번 줄어들지 않아 (Java)

#2688 줄어들지 않아

난이도 : 골드 5

유형 : DP

2688번: 줄어들지 않아

▸ 문제

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다. 

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

▸ 출력

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

 

 

 

문제 풀이 🖋  

dp 점화식을 세워서 푸는 문제이다. n자리 수의 개수를 구하는데 줄어들지 않는 경우의 수를 구하면 된다.

 

✔︎ 조건

  ∙ 테스트 케이스 수 : T (1<= T <= 1,000)

  ∙ n자리 수 (1 <= n <= 64)

 

arr배열로 차근차근 점화식의 형태를 만들어보자.

 

n==1, [ 0, 1, ..., 9]  → 10  

  ☛ arr[1] = 10이다.

 

n==2, [ 00 , 01, ... , 09] → 10

           [ 11, 12, ..., 19] → 9

            ...

           [99] → 1

  ☛ dp[2] = 1 + 2 + ... + 10 = 55이다.

 

n==3, [000, 001, 002, ..., 009] +   [011, 012 , ... , 019]  + [022, 023, ..., 029] + .. + [099] → (1~10의 합) 55

           [111, 112, 113, ..., 119] +   [122, 123 , ... , 129]  + [133, 134, ..., 139] + .. + [199] → (1~9의 합) 45

           ...

           [999] → (1의 합) 1

  ☛ arr[3] = 1 + 3 + ... + 46 + 55 = 220이다.

       

위의 과정을 보면 n이 1씩 증가함에따라 맨앞에 숫자 0~9를 대입한다고 보면 된다. 그렇다면 변수는 n과 새롭게 추가되는 즉 맨앞의 숫자 2가지를 신경쓰면 된다. 

 

이차원 배열을 arr[자릿수][맨앞의 숫자]로 설정하자.

그렇다면 위의 dp[]배열은 다음과 같이 변한다.

 

  n==1, [0], [1], ..., [9]

  ☛ arr[1][0] =1, dp[1][1] =1, ... , dp[1][9] =1  →  dp[1]의 합 10 

 

  n==2,  [ 00 , 01, ... , 09] → 10

              [ 11, 12, ..., 19] → 9

              ...

  ☛ arr[2][0] =10, arr[2][1] =9, ... , arr[2][9] =1  →  dp[2]의 합 55

 

따라서, arr[n][i] = (arr[n-1][0~i]의 합)이 된다.

직관적으로 나타내기 위해 i : n자릿수, j : 맨 앞에 (9-j)가 추가될 경우의 수로 설정했다.  

(* 원래 내 위의 설명대로라면 dp[i][9] =1이 맞지만 직관적인 코드를 위해 j -> (9-j)로 0 <-> 9 방향을 바꿔서 넣었다.)

 

이를 dp점화식으로 세워 값을 저장하여 계산하면 다음과 같다.

for(int i=0; i<n+1; i++) {
	dp[i][0] =1;
}
for(int i=0; i<10; i++) {
	dp[1][i] = 1;
}
		
for(int i=2;i<n+1;i++) {
	for(int j=1; j<10; j++) {
		dp[i][j] = dp[i-1][j] + dp[i][j-1];
	}
}

 

   

풀이 코드 ✔︎ 

import java.io.*;

public class Main {
	
	static long[][] dp;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=0; t<tc; t++) {
			int n = Integer.parseInt(br.readLine());
			dp = new long[n+1][10];
			System.out.println(solve(n));
			
			
		}
	}
	
	static long solve(int n) {
		long sum=0;
		for(int i=0; i<n+1; i++) {
			dp[i][0] =1;
		}
		for(int i=0; i<10; i++) {
			dp[1][i] = 1;
		}
		
		for(int i=2; i<n+1; i++) {
			for(int j=1; j<10; j++) {
				dp[i][j] = dp[i-1][j] + dp[i][j-1]; 
			}
		}
		
		for(long num : dp[n]) {
			sum +=num;
		}	
		return sum;
	}
}