[프로그래머스] N으로 표현

문제

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

코딩테스트 연습 - N으로 표현

문제해결방법

이 문제는 N을 사용한 횟수를 기준으로 잡고 DP로 풀었다

DP[N] = (DP[N-1], DP[1]) (DP[N-2], DP[2]) .... (괄호 안에 있는 DP의 원소끼리 사칙연산을 해준다)

코드

package Programmers;
 
import java.util.HashSet;
import java.util.Set;
 
public class Solution_N으로표현 {
    
    public static int cal(int x, int y, int n) {
        int result = 0;
        if(n==0) result = x*y;
        else if(n==1) result = x+y;
        else if(n==2) result = x/y;
        else result = x-y;
        return result;
    }
    
    public static int solution(int N, int number) {
        int answer = Integer.MAX_VALUE;
        Set<Integer>[] dp = new Set[9];
        int temp = N;
        for(int i=1; i<dp.length; i++) {
            dp[i] = new HashSet<>();
            dp[i].add(temp);
            if(temp==number && answer > i) answer = i;
            temp = temp*10+N;
        }
        loop:for(int i=2; i<dp.length; i++) {
            for(int x = 1; x<i; x++) {
                int y = i-x;
                for(int xKey : dp[x]) {
                    for(int yKey : dp[y]) {
                        for(int n=0; n<4; n++) {
                            if(n==2 && yKey==0) continue;
                            int num = cal(xKey, yKey, n);
                            if(num<0) continue;
                            if(!dp[i].contains(num)) {
                                dp[i].add(num);
                                if(num==number) {
                                    if(answer>i) answer=i;
                                    break loop;
                                }
                            }
                        }
                    }
                }
            }
        }
        if(answer == Integer.MAX_VALUE) answer = -1;
        return answer;
    }
    public static void main(String[] args) {
        int N = 5;
        int number = 12;
        System.out.println(solution(N, number));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.