문제설명
아래와 같이 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 |
입출력 예 설명
예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.
동적 계획 법이란?
DP의 개념이 부족했기 때문에 다른 분의 풀이를 참고하여 풀었다.
링크
나무위키의 설명에 의하면
파이썬 알고리즘 인터뷰
"특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법" 이라고 정의하며 이광근 교수는 DP의 본질적의미를 살려 기억하며 풀기로 정의 하였다.
피보나치 수열의 예를 들면 재귀적인 접근법은 연산마다 수많은 스택을 쌓아서 다시 연산하는 과정을 거치지만 동적프로그래밍은 이전 연산을 저장해 두기 때문에 접근방식은 비슷하지만 시간복잡도에서 유리하다.
DP에서는 문제를 어떻게 잘게 쪼갤 것인지 이를 어떻게 저장하여 참조할 것인지를 중점적으로 생각해 야되는 것같다.
풀이
주어진 숫자 N을 8번 미만으로 활용하여 사칙연산을 했을 시 목표값을 구할 수 있는지 없는지, 또 목표값을 구할 수 있는 N의 최소 사용횟수를 묻는 문제다.
문제를 쪼개보자
1. 5를 한번 사용했을 때 표현할 수 있는 값은 5이다.
2. 5를 두번 사용했을 때 표현할 수 있는 값은
55, 5+5,5-5,5*5,5/5로 1번에서 구한 사칙연산과 자기자신을 두번 사용한 수의 합집합니다.
3. 5를 세번 사용했을 때 표현할 수 있는 값은
555, 1번과 2번의 사칙 연산과 2번과 1번의 사칙연산의 합집합이 될 것이다.
물론 덧셈이나 곱셈은 차이가 없지만 뺄셈시 차이가 생긴다. 자료구조를 TreeSet을 통해 메모이제이션을 사용한 이유는 (곱셈과 덧셈연산 값)중복을 허용하지 않고 탐색이 빠르기 때문이다.
코드는 오름차순으로 N을 사용한 횟수를 인덱스로 갖는 TreeSet 배열을 생성하고 회차마다 사칙연산의 결과 값을 TreeSet[i]에 추가하고 목표값을 포함하고 있는지를 체크하고 있으면 인덱스 값을 출력한다. for문을 8번 순환했을 시에도 목표값을 탐색하지 못했다면 제한 사항에 따라 -1을 출력하게 된다.
메서드 solve는 메모제이션과 연산을 담당하는 함수로 static TreeSet[]에 for문의 횟차마다 연산 값을 저장해주고 호출시 다시 연산하는 것이 아니라 저장한 값을 return 하여 시간 복잡도를 낮춘다.
import java.util.*;
class Solution {
static TreeSet<Integer>[] dp;
static int _N;
public int solution(int N, int number) {
_N= N;
dp = new TreeSet[10];
for(int i=1;i<=8;i++){
solve(i);
if(dp[i].contains(number)) return i;
}
return -1;
}
static TreeSet solve(int i){
if(dp[i]!=null&&!dp[i].isEmpty()) return dp[i];
int NN=0;
for(int j=0;j<i;j++) NN = 10*NN+_N;
TreeSet<Integer> tmp = new TreeSet<>();
tmp.add(NN);
for(int n=1;n<i;n++){
int j= i-n;
TreeSet<Integer> from = solve(n);
TreeSet<Integer> to = solve(j);
for(int n1 : from){
for(int n2 : to){
tmp.add(n1+n2);
tmp.add(n1-n2);
tmp.add(n1*n2);
if(n2!=0) tmp.add(n1/n2);
}
}
}
return dp[i]=tmp;
}
}