문제 출처

코딩테스트 연습 > 동적계획법(Dynamic Programming) > N으로 표현
https://school.programmers.co.kr/learn/courses/30/lessons/42895

문제 설명

숫자 N과 number가 주어질 때, N과 사칙연산만으로 number을 표현할 때, N 사용횟수가 최솟값을 return 하라.

접근 방법

문제의 가장 큰 핵심은 DP를 이용할 때, N을 사용한 횟수를 이용하여 DP에 저장하는 것이다.

예를 들어
N을 1회 사용하는 수는 N 1개이다.
N을 2회 사용하는 수는 N+N , N-N, NN, N/N이다.
N을 3회 사용하는 수는 "2회 사용하는 수 ("+", "-", "*", "/") 이다.
...
이렇게 N을 8회 사용하는 수까지 DP에 저장하고, 이 저장하는 과정에서 DP 안에 number가 있는지 조회한다.

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        if (N == number) return 1;

        List<Set<Integer>> dp = new ArrayList<>();
        
        for (int i = 0; i <= 8; i++) {
            dp.add(new HashSet<>());
        }

        for (int i = 1; i <= 8; i++) {
            int num = Integer.parseInt(String.valueOf(N).repeat(i));
            dp.get(i).add(num);
            
            for (int j = 1; j < i; j++) {
                for (int num1 : dp.get(j)) {
                    for (int num2 : dp.get(i - j)) {
                        dp.get(i).add(num1 + num2);
                        dp.get(i).add(num1 - num2);
                        dp.get(i).add(num1 * num2);
                        if (num2 != 0) dp.get(i).add(num1 / num2);
                    }
                }
            }
            
            if (dp.get(i).contains(number)) return i;
        }

        return -1;
    }
}

Review
for(int num2 : dp.get(i-j))인 이유는
만약 i가 5일 때, j가 1,2,3,4 인 경우를 모두 해야하기 때문이다.

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        int answer = 0;
        List<Set<Integer>> dp = new ArrayList<>();

        // N을 사용한 횟수 1~8까지 List에 Set 생성
        for(int i = 0; i<=8; i++){
            dp.add(new HashSet());
        }

        // NN, NNN ... 숫자 list에 삽입
        for(int i = 1; i<=8; i++){
            int num = Integer.parseInt(String.valueOf(N).repeat(i));
            dp.get(i).add(num);

            // List, Set에 실제 값 저장
            for(int j=1; j< i; j++){
                for (int num1 : dp.get(j)){
                    for(int num2 : dp.get(i-j)){
                        dp.get(i).add(num1+num2);
                        dp.get(i).add(num1-num2);
                        dp.get(i).add(num1*num2);
                        if(num2 != 0) dp.get(i).add(num1/num2);
                    }
                }
            }
            if(dp.get(i).contains(number)) return i;
        }
        return -1;
    }
}

알게된 점

"N을 사용한 횟수"에 따라 DP를 진행하는 점을 떠올리지 못 했다.
처음 문제를 보았을 땐, 어떻게 풀지 고민하다가
N : 5 / number : 12 인 경우에 진행할 수 있는 Top-Down에서 가장 적은 횟수, Bottom-Up에서 가장 적은 횟수를 비교해서 풀려고 했으나, 이는 어떤 것이 가장 적은 횟수인지도 모르고, 이를 DP에 활용하기도 어려워 풀지 못했다.

문제푼 흔적

Review