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

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

프로그래머스

문제 유형

• 다이나믹 프로그래밍
  
  

문제 풀이

이 문제는 동적계획법, 즉 다이나믹 프로그래밍 을 이용하여 해결할 수 있다.

처음에는 문제에서 주어진 number 와 관련된 점화식을 세워 접근하려 했으나 쉽지 않았다.
그래서 N 의 사용횟수에 따라 가능한 값을 구하는 방식을 사용했다.

이해를 돕기위해 한가지 예를 들어보자.
N 이 5일 때, N 의 사용횟수에 따라 가능한 값들은 아래와 같다.

N의 사용횟수 1 = 5
N의 사용횟수 2 = 55, 10(5 + 5), 25(5 * 5), 1(5 / 5)
N의 사용횟수 3 = 555, 15(10 + 5), 5(10 - 5), 50(10 * 5), 2(10 / 5), 30(25 + 5) ..
..

위와 같이 사칙연산을 사용해서 N 의 사용횟수에 따라 가능한 값들을 구하는데,
이 때 주의해야할 점이 있다.
사용횟수별로 5, 55, 555와 같이 사용횟수만큼 각 자릿수가 N 으로 되어있는 수들도 있으므로,
잊지말고 꼭 추가해줘야 한다.

문제에서 N 의 사용횟수가 8보다 큰 경우 -1을 return 하라고 명시되어 있으므로,
N 의 사용횟수가 1부터 8일 때 가능한 값들 중 number 가 포함되어 있는지만 확인한다면,
문제를 해결할 수 있다.

소스 코드

import java.util.*;

class Solution {

    public int solution(int N, int number) {        
        ArrayList<Set<Long>> list = new ArrayList<>();
        for (int i = 0; i <= 8; i++) {
            list.add(new HashSet<Long>());
        }

        for (int i = 1; i <= 8; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 1; j <= i; j++) {
                sb.append(String.valueOf(N));
            }
            list.get(i).add(Long.parseLong(sb.toString()));

            for (int j = 1; j < i; j++) {
                for (long n1 : list.get(j)) {
                    for (long n2 : list.get(i - j)) {
                        if (n2 == 0) continue;

                        list.get(i).add(n1 * n2);
                        list.get(i).add(n1 / n2);
                        list.get(i).add(n1 + n2);
                        list.get(i).add(n1 - n2);
                    }
                }
            }

            if (list.get(i).contains((long) number)) return i;
        }

        return -1;
    }
}