[프로그래머스] N으로 표현(동적계획법)

1. 문제를 이해한다
- 괄호와 사칙 연산을 이용하여 number를 n으로 표현한다. 그 중 n이 사용된 횟수가 가장 적은 경우의 횟수를 결과값으로 돌려준다.
- n : 1 ~ 9 사이의 정수 n이 주어진다. 
- number : 32000이하의 정수가 주어진다. 

2. 문제를 재정의한다.
- number(k) = (n이 k번 사용되어 나온 결과 값) = number(j) [+, -, *, /] number(k-j) (단,  j 는 1보다 크고 k보다 작다.  k-j는 0이 아니다.)

3. 문제 풀이를 계획한다
1) number(1)의 집합을 구한다 : {n} (주어진 n 1개로 이루어진 집합)
2) number(2)의 집합을 구한다 : {n} [+, -, *, /] {n}
...
n) number(k)의 집합을 구한다.
* number(k)의 집합은 Set으로 구현하여 중복을 제거한다.
* number(k)의 집합을 구하는 과정에서 주어진 number와 값이 같은 경우가 있을 경우 k값 반환 

4. 문제 풀이를 검증한다.
- 

5. 구현한다.

public static int solution(int N, int number) {
		/*
		 *  8개의 HashSet을 만든다. (0번째 HashSet은 사용하지 않음) 
		 */
		HashSet[] sets = new HashSet[9];
		for(int i=0; i<sets.length; i++) {
			sets[i] = new HashSet<Integer>();
		}
		/*
		 *  5, 55, 555, 5555 와 같은 값들은 연산의 결과 값이 아니므로
		 *  연산 이전에 미리 Set에 포함시킨다.
		 */
		for(int i=1; i<sets.length; i++) {
			String enumerate = "";
			for(int j=0; j<i; j++) {
				enumerate += N;
			}
			sets[i].add(new Integer(enumerate));
		}
		
		/*
		 * i 번째 set을 구한다.
		 * j번째 set과 (i-j)번째set을 사칙연산하여 결과 값을 i번째 set에 더한다. 
		 */
		for(int i=1; i<sets.length; i++) {
			for(int j=1; j<i; j++) {
				HashSet<Integer> preSet = sets[j];
				HashSet<Integer> postSet = sets[i-j];
				for(int k : preSet) {
					for(int l : postSet) {
						sets[i].add(k + l);
						sets[i].add(k * l);
						sets[i].add(Math.abs(k - l));
						if(l != 0) sets[i].add(k / l);
					}
				}
			}
			System.out.println(i + "set !!");
			System.out.println(sets[i]);
			if(sets[i].contains(number)) return i;
		}
		/*
		 * 8번째 set안에 포함되지 않았다는 것은 n이 9번 이상 필요하다는 것이므로
		 * -1을 반환한다. 
		 */
        int answer = -1;
        return answer;
    }

6. 회고한다.
 풀이 방법을 몰랐을 때는 엄한 방식으로 삽질하면서 "내가 풀 수 있는 수준인가" 싶었는데, 방법을 알고 한 단계 한 단계 풀어보니 생각보다 간단하다..