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

문제 설명

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

문제 풀이

• DP를 이용하여 풀이하였다.
• DP[K] = K자리로 만들 수 있는 수들을 모아논 리스트

  DP[1] ~ DP[8] 까지 차례대로 구해보며 점화식을 도출해보자.

  • DP[1] -> N
  • DP[2] -> NN, DP[1]-DP[1] 간의 사칙연산 결과 (이하 DP[n]-DP[m])
  • DP[3] -> NNN, DP[1]-DP[2], DP[2]-DP[1]
  • ....
  • DP[5] -> NNNNN, DP[1]-DP[4], DP[2]-DP[3], DP[3]-DP[2], DP[4]-DP[1]

• 위와 같은 규칙을 이용하여 DP 테이블을 체우고 number에 해당하는 숫자가 등장하면 멈춘다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public List<List<Integer>> dp = new ArrayList<>();

    public int solution(int N, int number) {
        //초기화
        for (int i = 0; i <= 8; i++)
            dp.add(new ArrayList<>());

        //1개를 사용할 경우
        if (N == number) return 1;
        dp.get(1).add(N);

        //2개 사용할 경우 ~ 8개 사용할 경우
        for (int i = 2; i <= 8; i++) {
            //NNNNN 형태
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                tmp += (Math.pow(10, j) * N);
            }
            if (tmp == number) return i;
            dp.get(i).add(tmp);

            //dp[j] - dp[i - j] 끼리 연산
            for (int j = 1; j < i; j++) {
                for (int a = 0; a < dp.get(j).size(); a++) {
                    for (int b = 0; b < dp.get(i-j).size(); b++) {
                        int numA = dp.get(j).get(a);
                        int numB = dp.get(i-j).get(b);
                        //4가지 사칙연산 적용
                        tmp = numA + numB;
                        if (tmp == number) return i;
                        dp.get(i).add(tmp);
                        tmp = numA - numB;
                        if (tmp == number) return i;
                        dp.get(i).add(tmp);
                        tmp = numA * numB;
                        if (tmp == number) return i;
                        dp.get(i).add(tmp);
						//divby 0 에러 제거 
                        if (numB == 0) continue;
                        tmp = numA / numB;
                        if (tmp == number) return i;
                        dp.get(i).add(tmp);
                    }
                }
            }
        }
        return -1;
    }
}