[프로그래머스] N으로 표현

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   다음과 같이 5와 사칙연산만으로 12를 표현할 수 있으며 이 중에서 5를 가장 적게 사용한 경우는 4이다.

 

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

 

   이처럼 사용할 숫자 N과 number(만들어야 하는 대상)가 주어질 때 N 사용횟수의 최솟값을 구하는 문제이다. 제한 사항은 다음과 같다.

 

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

---

접근 방식

   DP의 개념을 이용해 문제를 해결하였다. 위에서 소개한 예제인 5를 이용해 50을 만드는 과정에 대해서 살펴보자. 먼저 5가 1개인 경우를 생각해보자. 숫자 5 1개를 이용해 만들 수 있는 수는 5 하나뿐이다.

 

 

   그럼 2개를 이용해서 만들 수 있는 경우를 알아보자. 사칙연산을 이용한 4가지 경우와 숫자 5만을 이용한 1가지 경우를 구할 수 있다.

 

 

   다음은 3개를 이용해 만들 수 있는 경우를 구해보자. 지금부턴 사칙연산을 수행하는 순서도 중요해진다. 3개를 이용해 만드는 경우는 1개로 만들 수 있는 경우의 숫자에 2개로 만들 수 있는 경우의 숫자를 연산하는 경우와 2개로 만들 수 있는 경우의 숫자에 1개로 만들 수 있는 경우의 숫자를 연산하는 경우가 달라지기 때문이다.

   중복되는 경우도 많아지며 분모가 0인 경우도 발생한다. 숫자 3개로만 만들 수 있는 경우도 까먹으면 안 된다.

 

 

   3개를 이용해 만들 수 있는 경우를 정리하면 다음과 같다.

 

 

   4개를 이용할 때의 경우는 '1과 3, 2와 2, 3과 1, 사칙연산없이 4개만을 이용한 경우'로 구할 수 있다. 즉, X개를 이용해 만들 수 있는 숫자들은 이전에 만들어둔 숫자들의 조합을 이용해 만들어지는 것이다. 따라서 X - 1개로 만들어진 값들을 중복을 제거한 형태로 저장해두고 참조하는 형태로 갱신해 나가야 한다.

   처음에 구하고자 했던 값은 50이므로 3개를 이용해 구할 수 있는 숫자에 포함된다. 따라서 진행한 X개(지금은 3개)를 반환하면 된다.

 

※ 문제에 최솟값이 8보다 크면 -1을 반환하는 조건이 있다. X개를 8까지 증가시켜 나가는 과정에서 원하는 숫자(number)를 발견하지 못 하면 -1을 반환하면 된다.

---

코드

import java.util.HashSet;
import java.util.Set;

public class 프로그래머스42895번 {
    public int solution(int N, int number) {
        //중복 제거를 위해 Set을 사용하였으며
        //Set의 인덱스 번호는 사용한 N의 개수를 의미
        //Set에는 N을 index개 만큼 이용해서 만들 수 있는 값들이 저장 
        Set<Integer>[] valid = new Set[9];
        //사칙연산 없이 순수하게 N을 이용해 만들 수 있는 경우
        //ex) 5 55 555 ...
        int validNum = 0;

        for (int i = 1; i <= 8; i++) {
            valid[i] = new HashSet<>();
            //사칙연산없이 N만을 이용해 만들 수 있는 경우 저장
            validNum = 10 * validNum + N;
            valid[i].add(validNum);
            //N을 3개 이용해서 만들 수 있는 값들은 아래 두 가지 순서로 연산한 경우가 해당됨
            //1. N을 1개 이용해서 만들 수 있는 경우 , N을 2개 이용해서 만들 수 있는 경우
            //2. N을 2개 이용해서 만들 수 있는 경우 , N을 1개 이용해서 만들 수 있는 경우
            for (int j = 1; j < i; j++) {
                for (int num1 : valid[j]) {
                    for (int num2 : valid[i - j]) {
                        //뽑은 유효 숫자를 이용해 사칙연산 수행
                        //나눗셈의 경우 분모가 0인 경우를 주의
                        valid[i].add(num1 + num2);
                        valid[i].add(num1 - num2);
                        valid[i].add(num1 * num2);
                        if (num2 != 0)
                            valid[i].add(num1 / num2);
                    }
                }
            }
            //현재 이용한 N의 개수에서 원하는 숫자(number)가 만들어진 경우
            //연산 종료 및 사용한 개수 반환
            if (valid[i].contains(number))
                return i;
        }
        //N을 8개 이용한 경우까지 원하는 숫자를 만들지 못한 경우 -1 반환
        return -1;
    }
}