99클럽 코테 스터디 18일차 TIL - DP (프로그래머스 'N으로 표현')

항해99 코테 스터디 18일차 문제인 프로그래머스의 'N으로 표현'은 주어진 숫자 N과 사칙연산을 이용해 목표 숫자를 만드는 데 N이 최소 몇개 사용되는지를 구하는 문제다. 난이도는 레벨3이며 DP를 통해 해결할 수 있다.

 

오늘의 문제 - N으로 표현 문제 정보

문제 키워드

- DP

난이도

- Level 3

 

문제 요약

• 1~9 사이의 정수 N과 목표 숫자 number가 주어진다.
• N과 사칙연산을 가지고 number를 만들 때, 필요한 N의 최소 갯수를 구하라.

 

문제 풀이 과정  

• N의 개수마다 만들 수 있는 숫자들을 dp 맵에 저장한다.
• dp[cnt]를 구할 때, dp[cnt-1] (op) dp[1], dp[cnt-2] (op) dp[2], …를 이용한다.

코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        if (N == number) return 1;
        
        Map<Integer, Set<Integer>> dp = new HashMap<>(); 
        dp.put(1,Set.of(N));
        
        int nnn = N;
        
        for(int i = 2; i <= 8; i++){
            Set<Integer> set = new HashSet<>();
            
            // 이전 계산 결과들과 상관없이 N의 연속으로 이루어진 숫자 추가
            nnn = nnn*10+N;
            set.add(nnn);
            
            // dp[i]를 구하기 위해 dp[i-1]*dp[1], dp[i-2]*dp[2], ...의 연산 결과들을 모두 구함
            for(int j=1; j < i; j++){
                set.addAll(calculate(dp.get(j), dp.get(i-j)));
            }
            
            if (set.contains(number)) {
                return i;
            }
            
            dp.put(i, set);
        }
        
        return -1;
    }
    
    public Set<Integer> calculate(Set<Integer> nums1, Set<Integer> nums2){
        Set<Integer> results = new HashSet<>(); 
        for(int num1: nums1){
            for(int num2: nums2){
                results.add(num1 + num2);
                results.add(num1 - num2);
                results.add(num1 * num2);
                if(num2 !=0){
                    results.add((int) num1 / num2);
                }
            }
        }
        
        return results;
   }
}

• 시간복잡도: ?
• 공간복잡도: ?

 

오늘의 학습 회고

새롭게 알게된 것

• DP는 역시 아이디어를 떠올리는 게 제일 힘들다...! 많이 문제를 풀면서 익히자.