백준 1443번 망가진 계산기 (JAVA)

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

1443번: 망가진 계산기

 

저는 dfs를 통해 문제를 해결하였습니다.

dfs를 통해 2~9까지 곱하는 경우를 전부 진행하였고, 길이가 d보다 길면 더 이상 진행하지 않도록 하였고, depth가 p라면 현재 값을 리턴하여 답을 구하였습니다.

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1443 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int d = stoi.apply(st.nextToken());
        int p = stoi.apply(st.nextToken());
        long limit = 1;
        for(int i = 0 ; i < d; i++){
            limit *= 10;
        }
        Set<String> visited = new HashSet<>();
        long result = cal(0,1,p,limit,visited);
        System.out.println(result);
    }

    private static final int[] NUMBERS = {2,3,4,5,6,7,8,9};
    private static final long NOT_VALID = -1;

    private static long cal(int depth, long now, int p, long limit, Set<String>visited) {
        if(depth == p){
            return now;
        }
        if(now >= limit){
            return NOT_VALID;
        }
        long result = NOT_VALID;
        for(int number : NUMBERS){
            if(now * number < limit){
                if(visited.contains(Arrays.toString((new long[]{depth+1,now*number})))){
                    continue;
                }
                visited.add(Arrays.toString((new long[]{depth+1,now*number})));
                long temp = cal(depth+1,now * number,p,limit,visited);
//                if(temp == NOT_VALID){
//                    break;
//                }
                result = Math.max(result, temp);
            }else{
                break;
            }
        }
        return result;
    }
}