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

문제설명

아래와 같이 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 합니다.
  
  

해결 방법

DP로 풀었다. DP의 적용패턴을 아래와 같다.

 

숫자를 1개 사용했을 때 표현가능한 숫자는

 

N하나이다.

 

 

숫자를 2개 사용했을 때 표현가능한 숫자는

 

n을 두번 이어붙인 수와

 

숫자를 1개 사용했을 때 표현 가능한 숫자들과 숫자 1개를 사용했을 때 표현 가능한 숫자들의 사칙연산 결과이다. 

 

 

숫자를 3개 사용했을 때 표현가능한 숫자는

 

N을 세번 이어붙인 수와

 

숫자를 1개 사용했을 때 표현 가능한 숫자들과 숫자 1개를 사용했을 때 표현 가능한 숫자들의 사칙연산 결과 U

 

숫자를 2개 사용했을 때 표현 가능한 숫자들과 숫자 1개를 사용했을 때 표현 가능한 숫자들의 사칙연산 결과이다.

 

 

숫자를 n개 사용했을 때 표현 가능한 숫자는

 

N을 n번 이어붙인 수와

 

숫자를 1개 사용했을 때 표현 가능한 숫자들과 숫자 1개를 사용했을 때 표현 가능한 숫자들의 사칙연산 결과 U

 

숫자를 2개 사용했을 때 표현 가능한 숫자들과 숫자 1개를 사용했을 때 표현 가능한 숫자들의 사칙연산 결과 U

 

숫자를 2개 사용했을 때 표현 가능한 숫자들과 숫자 2개를 사용했을 때 표현 가능한 숫자들의 사칙연산 결과 U

 

...

 

숫자를 n-1개 사용했을 때 표현 가능한 숫자들과 숫자 1개를 사용했을 때 표현 가능한 숫자들의 사칙연산 결과이다.

 

정리했을 때,

 

숫자를 a, b번 사용했을 때 나타낼 수 있는 숫자를 집합 A[a], B[b]라고 하면

(1 <= a, b <= n-1, a + b <= n)

 

숫자를 n번 사용해서 나타낼 수 있는 숫자들은 숫자를

 

n번 이어붙인 숫자와

 

[A[1] <사칙연산> B[1]] U [A[1] <사칙연산> B[2]] U .... U [A(a) <사칙연산> B[b]]의 결과와 같다.

 

JAVA

package programmers;

import java.util.*;

public class p_42895 {
	public static int solution(int n, int num) {
		int ans = 0;
		ArrayList <HashSet<Integer>> list = new ArrayList<>();
		HashSet <Integer> set = new HashSet<>();
		set.add(n);
		list.add(set);
		
		while(ans < 8) {
			if(list.get(ans).contains(num)) break;
			ans++;
			
			HashSet <Integer> nset = new HashSet<>();
			String s = "";
			for(int i = 0; i < ans + 1; i++) s += String.valueOf(n);
			nset.add(Integer.parseInt(s));
			
			for(int i = 0; i <= ans / 2; i++) {
				for(int j = 0; i + j < ans; j++) {
					for(Iterator it1 = list.get(i).iterator(); it1.hasNext();) {
						int op1 = (int)it1.next();
						for(Iterator it2 = list.get(j).iterator(); it2.hasNext();) {
							int op2 = (int)it2.next();
							nset.add(op1 + op2);
							nset.add(op1 - op2);
							nset.add(op1 * op2);
							if(op2 != 0) nset.add(op1 / op2);
						}
					}
				}
			}
			list.add(nset);
		}
		
		return (ans >= 8) ? -1 : ans + 1;
	}
	public static void main(String[] args) {
		int n = 5;
		int num = 12;
		int n2 = 9;
		int num2 = 32490;
		
		System.out.println(solution(n, num));
	}
}