[프로그래머스/Java] N으로 표현(DP 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 동적계획법(DP) 파트 문제인 N으로 표현을 자바로 풀어보았다. 

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

프로그래머스

 

 

 처음에 점화식을 찾는 데에 상당히 오랜 시간이 걸렸다. 그것만 찾고 나면 코드 자체는 어렵지 않게 쓸 수 있다. 대체로 DP 문제들이 점화식 찾는 게 어렵고 그 뒤는 크게 어렵지 않게 해결 가능한 것 같다.

 이 문제의 기본적인 해결 방법은 동적 배열의 i번째 인덱스에, N을 i번 사용하여 만들 수 있는 숫자들의 set을 저장하는 것이다. 그리고 그 숫자들의 set은 j번째 set과 i-j번째 set의 사칙연산으로 찾을 수 있다. 이것만 이해하면 코드를 어렵지 않게 이해할 수 있다. 다만 주의할 점은 N이 반복되는 i자리 숫자도 따로 넣어줘야 하는 것이다. 이건 사칙연산으로 찾을 수 없으므로, 아래 코드에서와 같이 cur.add(Integer.parseInt(String.valueOf(N).repeat(i))); 를 이용해서 따로 추가해주었다. 

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        List<Set<Integer>> dp = new ArrayList<>();
        dp.add(new HashSet<Integer>());
        dp.get(0).add(0);
        
        // i = 해당 인덱스set 내 숫자들을 만드는데 필요한 N의 갯수
        for (int i = 1; i <= 8; i++) {
            Set<Integer> cur = new HashSet<>();
            // N, NN, NNN을 저장 (N=2일때: 2, 22, 222 ...)
            cur.add(Integer.parseInt(String.valueOf(N).repeat(i)));
            
            // N을 i번 사용하여 만들 수 있는 숫자 저장
            for (int j = 1; j <= i/2; j++) {
                for (int n1 : dp.get(j)) {
                    for (int n2 : dp.get(i-j)) {
                        cur.add(n1 + n2);
                        cur.add(Math.abs(n1 - n2));
                        cur.add(n1 - n2);
                        if (n2 != 0) cur.add(n1 / n2);
                        if (n1 != 0) cur.add(n2 / n1);
                        cur.add(n1 * n2);
                    }
                }
            }
            
            // 우리가 찾고자 하는 number 있으면 i 바로 리턴
            if (cur.contains(number)) return i;
            dp.add(cur);
        }
        
        return -1;
    }
}