백준 : 1443 망가진 시계

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

1443번: 망가진 계산기

 

Solved 난이도에 비해서 시웠던 문제.

 

중간에 적절히 가지치기를 해주면서 경우의 수를 구하면된다.  30번 곱할때 수들을 뽑을수 있는 경우의수를 생각하자. 이때 8*8*2 == 2*8*8 는 같기때문에 수들을 내림차순으로 정렬한다고 생각하면 편할것이다.

 

import java.util.Scanner;

public class 망가진계산기 {
	static long N, P;
	static long ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		P = sc.nextInt();

		ans = 0L;

		dfs(1, 0, 9);
		ans = ans == 0 ? -1 : ans;
		System.out.println(ans);
	}

	public static void dfs(int num, int cnt, int start) {
		if ((num + "").length() > N)
			return;

		if (cnt == P) {
			ans = Math.max(ans, num);
			return;
		}

		for (int i = start; i >= 2; i--) {
			dfs(num * i, cnt + 1, i);
		}
	}
}