(Python, Java) 프로그래머스 - N으로 표현

21 Feb 2022 in Algorithm on Programmers, Level3

[문제 링크]

풀이

def solution(N, number):
    if N == number:
        return 1
    
    # n의 인덱스 개수로 만들 수 있는 경우의수
    # ex) 1번째 인덱스는 N 1개로 만들 수 있는 사칙연산 결과 경우의 수
    dp = [{0}, {N}]

    for count in range(2, 9):
        tmp = set()
        tmp.add(int(str(N) * count)) # count개수만큼 연달아서 사용한 N

        for i in range(1, count):
            for x in dp[i]:
                for y in dp[count - i]:
                    tmp.add(x + y)
                    tmp.add(x - y)
                    tmp.add(x * y)
                    if y != 0:
                        tmp.add(x // y)
        if number in tmp:
            return count
        dp.append(tmp)

    return -1

DP를 사용하는 문제이고 DP 문제인 것을 판단하는 것이 어려운 문제다.
예를 들어, N을 3번을 사용해서 만들 수 있는 수는 N을 1번 사용해서 만들 수 있는 수들과 N을 2번 사용해서 만들 수 있는 수들을 사칙연산해서 만든 수이다.

Java 풀이

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, new HashSet<>(List.of(N)));

        for (int cnt = 2; cnt < 9; cnt++) {
            Set<Integer> temp = new HashSet<>();

            // 연산 없이 N을 counter 개수만큼 이어 붙인 수 temp에 담기
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < cnt; i++) {
                sb.append(N);
            }
            temp.add(Integer.parseInt(sb.toString()));

            // cnt 개수만큼 N을 사용해서 만들 수 있는 모든 경우의 수 temp에 담기
            for (int k = 1; k < cnt; k++) {
                for (Integer x : dp.get(k)) {
                    for (Integer y : dp.get(cnt - k)) {
                        temp.add(x + y);
                        temp.add(x - y);
                        temp.add(x * y);
                        if (y != 0)
                            temp.add(x / y);
                    }
                }
            }

            if (temp.contains(number))
                return cnt;
            dp.put(cnt, temp);
        }

        return -1;
    }
}