[JAVA] 프로그래머스 (Lv.3) N으로 표현

링크

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

---

문제 설명

아래와 같이 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

---

풀이

사칙연산에서 N이 사용된 횟수에 따라 케이스를 나눈다.

예제를 기준으로 하면 다음과 같다.

• 1번
  • 5
• 2번
  • 5 + 5
  • 5 - 5
  • 5 * 5
  • 5 / 5
  • 55
• 3번
  • (5 + 5) + 5
  • (5 + 5) - 5
  • (5 + 5) * 5
  • (5 + 5) / 5
    ...
  • 555

n번 사용된 경우의 수는 결국 n-2번, n-1번의 각 경우를 다시 사칙연산하면 된다. 그리고 숫자 N으로만 이루어진 숫자를 포함하면 된다.

N이 4번 사용된 경우를 구하려면 결국 (1번, 3번), (2번, 2번), (3번, 1번)의 각 원소를 각각 사칙연산하는 것이다. 단 연산된 결과 값은 중복이 필요 없으므로 Set 컬렉션을 이용한다.

dp를 리스트로 생성해 각 N이 사용된 횟수 별 사칙 연산의 값을 담아둔다. 그리고 N이 8번 사용될 때까지 값을 구해간다.

코드

//프로그래머스
class Solution {

    public int solution(int N, int number) {

        //N과 number이 같을 때
        if (N == number) return 1;

        List<Set<Integer>> dp = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            dp.add(new HashSet<>());
        }
        //dp = [[], [5], [], [], [], [], [], [], []]
        dp.get(1).add(N);

        for (int i = 2; i < 9; i++) {

            //N번째에 N개의 수 ex)2번째에 55
            StringBuilder sb = new StringBuilder().append(N);
            for (int j = 1; j < i; j++) {
                sb.append(N);                
            }
            dp.get(i).add(Integer.parseInt(sb.toString()));

            //N이 4개일 때는
            //(1 + 3), (2 + 2), (3 + 1)
            for (int j = 1; j < i; j++) {
                for (Integer num1 : dp.get(j)) {
                    for (Integer num2 : dp.get(i - j)) {
                        dp.get(i).add(num1 + num2);
                        dp.get(i).add(num1 - num2);
                        dp.get(i).add(num1 * num2);
                        if (num2 != 0) {
                            dp.get(i).add(num1 / num2);
                        }
                    }
                }
            }

            //사칙연산의 결과가 number일 경우 최소값으로 i를 반환
            if (dp.get(i).contains(number)) {
                return i;
            }

        }

        return -1;
    }
}

---