N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895

문제 분류가 dp라서 dp로 접근하려다가 계속 고민해봐도 안 풀리길래 dfs로 풀었다.

최댓값이 32,000이므로 N을 활용해서 최대 NNNNN까지 만든 후에 활용하면 된다.

이때, +와 *는 상관없지만, -와 /는 연산자를 기준으로 앞, 뒤의 순서에 영향을 받기 때문에 이 부분도 고려해준다.

사실 long을 쓸까 말까 하다가, int로 썼다.

import java.io.*;
import java.util.*;
 
public class Solution {
 
    static BufferedReader br;
    static BufferedWriter bw;
    
    static int Min = Integer.MAX_VALUE;
    static int[] seq;
    
    static void dfs(int answer, int cnt, int N, int number, String str)
    {
        if(cnt > 8) {
            return;
        }
 
        if(answer == number) {
            //System.out.println(str);
            Min = Math.min(Min, cnt);
            return;
        }
        
        for(int i=1; i<=5; i++) {
            dfs(answer + seq[i], cnt + i, N, number, str + "+" + Integer.toString(seq[i]));
            dfs(answer - seq[i], cnt + i, N, number, str + "-" + Integer.toString(seq[i]));
            dfs(answer * seq[i], cnt + i, N, number, str + "*" + Integer.toString(seq[i]));
            dfs(answer / seq[i], cnt + i, N, number, str + "/" + Integer.toString(seq[i]));
            dfs(seq[i] - answer, cnt + i, N, number, str + "-" + Integer.toString(seq[i]));
            if(answer != 0) dfs(seq[i] / answer, cnt + i, N, number, str + "/" + Integer.toString(seq[i]));
        }
    }
    
    static int solution(int N, int number) {    
        seq = new int[10];
        
        seq[1] = N;
        int ten = 10;
        for(int i=2; i<=5; i++) {
            String s = "";
            for(int j=0; j<i; j++) {
                s += Integer.toString(N);
            }
            seq[i] = Integer.parseInt(s);
        }
        
        for(int i=1; i<=5; i++) {
            dfs(seq[i], i, N, number, Integer.toString(seq[i]));
        }
        
        return Min == Integer.MAX_VALUE ? -1 : Min;
    }
    
    public static void main(String[] args) throws IOException  {
        // TODO Auto-generated method stub
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        //st = new StringTokenizer(br.readLine());
    
        bw.write(String.valueOf(solution(6, 11111)));
 
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}
 
class pair {
    int first, second;
    pair(int a, int b) {
        this.first = a;
        this.second = b;
    }
}
 
class tuple {
    int first, second, third;
    tuple(int a, int b, int c) {
        this.first = a;
        this.second = b;
        this.third = c;
    }
}
 
class PQ implements Comparable<PQ> {
    int first, second, third;
    
    PQ(int f, int s, int t) {
        this.first = f;
        this.second = s;
        this.third = t;
    }
    
    public int compareTo(PQ p) {
        if(this.first < p.first) {
            return -1; // 오름차순
        }
        else if(this.first == p.first) {
            if(this.second < p.second) {
                return -1;
            }
            else if(this.second == p.second) {
                if(this.third < p.third) {
                    return -1;
                }
            }
        }
        
        return 1; 
        // 이미 this.first가 더 큰 것이 됐으므로, 1로 해준다.
        // -1로 하면 결과가 이상하게 출력됨.
    }
}