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

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

코딩테스트 연습 - N으로 표현

풀이 방법

N을 1개 사용해서 만들 수 있는 표현식은 다음과 같다. 표현식을 계산한 값들의 집합을 SET1라고 하자.

1. N

N을 2개 사용해서 만들 수 있는 표현식은 다음과 같다. 표현식을 계산한 값들의 집합을 SET2이라고 하자. NN U SET1 op SET1와 같다.

1. NN
2. N + N
3. N - N
4. N * N
5. N / N

N을 3개 사용해서 만들 수 있는 표현식은 다음과 같다. SET3 = NNN U (SET1 op SET2) U (SET2 op SET1) 이다.

1. NNN
2. (N + N) +,-,*,/ N
3. (N - N) +,-,*,/ N
4. (N * N) +,-,*,/ N
5. (N / N) +,-,*,/ N
6. N +,-,*,/ (N + N)
7. N +,-,*,/ (N - N)
8. N +,-,*,/ (N * N)
9. N +,-,*,/ (N / N)

N을 4개 사용해서 만들 수 있는 표현식을 계산한 값들의 집합 SET4 = NNNN U (SET1 op SET3) U (SET2 op SET2) U (SET3 op SET1) 이다.

 

이를 일반화하면, SETn = NN...N U (SET1 op SET(n-1)) U (SET2 op SET(n-2)) U ... U (SET(n-1) op SET1)이다. 계산한 값들이 중복으로 저장되지 않도록 unordered_set을 사용하도록 한다.

unordered_set<int> cur_set;
num = num*10 + N;
cur_set.insert(num);
for(int i=0; i<n; i++){ // nth_set[i]
	for(int a: nth_set[i]){
		for(int b: nth_set[n-1-i]){
			cur_set.insert(a+b);
			cur_set.insert(a-b);
			cur_set.insert(a*b);
			if(b != 0) cur_set.insert(a/b);
		}
	}
}

 

SETn을 구한 후, 여기에 number가 포함된다면 n을 반환한다.

if(cur_set.find(number) != cur_set.end()) return n;

 

전체 코드는 여기서 확인할 수 있다.

 

참고 링크: https://gurumee92.tistory.com/164