프로그래머스 - N으로 표현 (DP)

문제 설명
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6, 5, 4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용 횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

 

입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

 

문제 접근

핵심 아이디어

• setList[i]를 N을 i번 사용해서 만들 수 있는 모든 정수의 집합으로 정의한다.
• 작은 i에서 구한 결과들을 조합(+,-,*,/)하여 더 큰 i의 결과를 만든다.
  → 동적 계획법(DP) 패턴.

자료구조 설계

• List<Set<Integer>> setList 크기를 9로 준비(인덱스 0~8).
  • 문제 조건: 사용 횟수의 최솟값이 8을 넘으면 -1 반환.
• 각 요소는 HashSet<Integer>로 중복을 자동 제거.

초기화

• setList.get(1).add(N)
  • N을 1번 사용하면 만들 수 있는 수는 N 하나뿐이므로, 1단계 집합은 {N}으로 시작.

점화식(구성 방법)

• i = 2..8에 대해 다음을 수행:
  1. 붙여쓰기(concat) 숫자 추가
     • concat = Integer.parseInt(String.valueOf(N).repeat(i))
     • 예: N=5, i=3 → 555
     • setList[i]에 우선 추가.
  2. 조합 연산으로 확장
     • i를 j와 i-j로 분할해,
       A ∈ setList[j], B ∈ setList[i-j] 모든 쌍에 대해를 setList[i]에 추가.
     • A + B, A - B, A * B, (B != 0이면) A / B
     • 이렇게 하면 “i번 사용”으로 만들 수 있는 모든 수가 누적된다.

정답 도출

• 모든 i(1..8)에 대해 집합을 만든 뒤,
  number가 포함된 가장 작은 i(= 최소 사용 횟수)를 반환.
  • 코드에선 for (Set<Integer> set : setList) ... 로 탐색.

 

알고리즘 코드

package com;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class N으로_표현 {
    public int solution(int N, int number) {
        List<Set<Integer>> setList = new ArrayList<>(); // Set<Integer>를 원소로 갖는 ArrayList -> 여러 개의 집합을 담고 있는 리스트
        // setList.get(0)은 HashSet<Integer>이고 setList.get(1)도 마찬가지이다. 이런식으로 9개가 들어간다.


        /**
         *
         * setList = [
         *     {},  // setList.get(0)
         *     {},  // setList.get(1)
         *     {},
         *     {},
         *     {},
         *     {},
         *     {},
         *     {},
         *     {}   // setList.get(8)
         * ]
         *
         * setList.get(i).add(값)이후 이런식으로 값을 너어주게 되는데
         *
         * setList.get(2).add(55); 이 코드를 실행 후엔
         * setList = [
         *     {}, {}, {55}, {}, {}, {}, {}, {}, {}
         * ] 이렇게 저장됨
         *
         *
         *  */
        for(int i = 0; i < 9; i++) {
            setList.add(new HashSet<>());
        }

        // 1회
        setList.get(1).add(N); // 즉 setList.get(1) → N을 1번만 사용했을 때 만들 수 있는 수들의 집합

        // 2회 이상
        for(int i = 2; i < setList.size(); i++) { // N을 2번 이상 사용했을 때부터 계산. setList의 size는 9니까 i는 2~8까지 반복
            int concat = Integer.parseInt(String.valueOf(N).repeat(i)); // NN, NNN, NNNN 같이 붙여쓰기 숫자를 직접 만들어줘야한다.
            Set<Integer> newSet = setList.get(i);
            newSet.add(concat); // newSet에 붙여쓰기 숫자를 먼저 집어 넣는다.

            for(int j = 1; j <= i; j++) {
                Set<Integer> setA = setList.get(j); // N을 j번 써서 만들 수 있는 수 집합
                Set<Integer> setB = setList.get(i - j); // N을 (i-j)번 써서 만들 수 있는 수 집합

                for(Integer numA : setA) {
                    for(Integer numB : setB) {
                        newSet.add(numA + numB);
                        newSet.add(numA - numB);
                        newSet.add(numA * numB);

                        if(numA != 0 && numB != 0) {
                            newSet.add(numA / numB);
                        }
                    }
                }
            }
        }

        for (Set<Integer> set : setList) {
            if(set.contains(number)) return setList.indexOf(set);
        }
        return -1;
    }
}