BOJ1038 감소하는 수(Java)

---

https://www.acmicpc.net/problem/1038

풀이 방법 : dp, 재귀

---

사고 과정

1년 전에 풀이 기록이 있는 문제였다.

아마 당시에는 수학으로 접근해서 풀었던 것 같은데, 기억이 잘 나지도 않고

Java도 연습할 겸 다시 풀어보았다.

dp[i][j] = i자리 숫자 중 j로 시작하는 감소하는 수의 갯수 로 놓고, 한 자리수의 경우는 전처리 해주었다.

두 번째 자리부터는 예를들어 세 자리 수 중 5 _ _ 이라면

4로 시작하는 세 자리 수의 갯수는 dp[2][0] + dp[2][1] + .. dp[2][5] 일 것이다.

이런 식으로 갯수를 더해주다가, 어느 순간 dp값이 N 이상이 되면 해당 앞자리수를 print로 출력하고,

방금 막 더한 수를 빼고 재귀 호출하여 그 다음에 올 숫자를 하나씩 print하였다.

---

예시로 사용한 케이스가 58인데,

0~9 : 9개, 10~98 : 1 + 2 + ... 9 = 45

210 이 55이고, 앞자리 3 으로 넘어오면 31x가 1개, 32x가 2개로 58개가 된다.

현재 dp[3][j]를 채우고 있고, dp[2][1]을 더한게 56(210이 55, 310이 56)

dp[2][2]를 더하는 순간 dp[3][j]값이 58이 된다.

앞자리가 확정된 3을 출력하고 재귀함수 find(58 - dp[2][2], i, j)를 호출한다.

재귀함수는 i - 1번째 자리를 더한다.

55부터 dp[2][0], dp[2][1], dp[2][2]를 다시 더해본다.

dp[2][1]은 통과하고 dp[2][2]에서 걸린다. 앞자리 2 확정 -> 2 출력

find(58 - dp[2][1], 2, 2) 호출

-> 56부터 다시 탐색,

dp[1][0](결과 320)이 57, dp[1][1]이 58번째. i가 1번째 자리로 끝났으므로 return.

정답은 321

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;


class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;
	static long N, ans;
	static int[][] dp = new int[11][10];

	public static void find(int cnt, int i, int j) {
		if (i - 1 > 0) {
			for (int o = 0; o < j; ++o) {
				cnt += dp[i - 1][o];
				if (cnt >= N) {
					System.out.print(o);
					find(cnt - dp[i - 1][o], i - 1, j - 1);
					return;
				}
			}
		}
	}

	public static boolean solve() {
		dp[1][0] = 1;
		int cnt = 0;
		for (int i = 1; i < 10; ++i) {
			dp[1][i]++;
			cnt++;
		}
		for (int i = 2; i < 11; ++i) {
			for (int j = i - 1; j < 10; ++j) {
				for (int k = 0; k < j; ++k) {
					dp[i][j] += dp[i - 1][k];
				}
				cnt += dp[i][j];
				if (cnt >= N) {
					System.out.print(j);
					find(cnt - dp[i][j], i, j);
					return true;
				}
			}
		}
		return false;
	}

	public static void main(String args[]) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();

		// st = new StringTokenizer(br.readLine().trim());
		N = Integer.parseInt(br.readLine());
		if (N < 10) {
			System.out.println(N);
		} else {
			if (!solve()) {
				System.out.println(-1);
			}
		}

	}
}

---

후기

너무 어렵게 푼 것 같다.

이렇게 하면 되지 않을까 -> 로직을 짜고 디버깅하면서 코드를 고쳤다.

이런 풀이법을 지양하고 머리를 더 쓰면서 문제를 풀어야 할 것 같다.