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

문제

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

 

예를 들어, 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자리 수의 개수를 출력한다.

 

 

풀이

다이나믹 프로그래밍을 이용하여 풀 수 있는 문제였습니다.

자리 수가 커질 때마다 이전 자리 수의 값보다 크거나 같도록 설정해 주는 수는 총 몇개가 있는지 구하는 것이 핵심이었습니다.

 

가령, 12345 와 11111 이 줄어들지 않는 수에 속합니다.

이와 같은 수가 각 자리 수마다 몇 개가 존재하는지 판단하면 됩니다.

 

1자리는 0 ~ 9가 있고, 모두 줄어들지 않는 수에 속하므로 총 10개입니다.

2자리는 00, 01, ... 09, 11, 12, ... 99 등이 줄어들지 않는 수에 속합니다.

이 때, 그 전 자리 수와의 규칙성이 있습니다.

 

예를 들어, 0으로 시작하는 2자리 수의 줄어들지 않는 수를 구해봅시다.

00, 01, ... , 09로 총 10개가 있습니다. 그리고 이것은 그 전 자리 수의 0부터 9까지 더한 것과 같습니다.

 

마찬가지로, 1로 시작하는 2자리 수의 줄어들지 않는 수를 구해봅시다.

11, 12, ..., 19로 총 9개가 있습니다. 그리고 이것은 그 전 자리 수의 1부터 9까지 더한 것과 같습니다.

 

정리하면, dp[i][j] = dp[i - 1][j] + dp[i - 1[j + 1] + ... + dp[i - 1][9] 로 정의할 수 있습니다.

여기서 i는 자리 수 이고, j는 시작하는 수로 생각하면 됩니다.

 

1자리일 때는 기저 사례로 생각하여, dp[1][0] ~ dp[1][9]는 모두 1로 초기화한 뒤, 위 점화식을 사용하여 다이나믹 프로그래밍을 수행하시면 끝입니다.

 

다만, 더하는 과정에서 오버플로우가 발생할 수 있으므로 자료형은 int[][]가 아닌, long[][]로 설정하고, 답을 출력할 때도 자료형을 long 타입의 변수를 사용하여야 합니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.