> 문제설명
아래와 같이 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 |
입출력 예 설명
예제 #1 문제에 나온 예와 같습니다.
예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.
> 풀이
DP인듯 BruteForce인듯.. 하여튼, 다음과같이 풀었다.
각 N의 개수에 대한 dp 리스트를 만들고(8까지만 구하면 되므로 dp는 8까지)
F(n) => F(n-1)@F(1), F(n-2)@F(2), … F(1)@F(n-1) ( 점화식 세우고 )
와 같은 식을 만들었다. @는 사칙연산 네가지를 포함한다. ( @는 문제의 식에서 괄호쯤 생각하면 될것이다. )
즉,
F(1) = N =>
1가지F(2) = F(1)@F(1) + (NN) => 1x1x4 + 1 =>
5가지F(3) = F(2)@F(1), F(1)@F(2)
=> 5x1x4 + 1x5x4 + (NNN)
=> 총 40가지 + (NNN) =>
41가지F(4) = F(3)@F(1), F(2)@F(2), F(1)@F(3)
=> 41x1x4 + 5x5x4 + 1x41x4 + (NNNN) =>
428가지dp[1] ~ dp[8] 까지 각 연속된 N을 추가해주고, @연산으로 연산된 값을 dp 리스트에 저장해주었다.
이런식으로 모든 경우의 수를 구해주었다. (ㅎㅎ..비효율적이겠지..?)
결국, n을 1부터 8까지 답이 나올때 까지 구해주었는데, 8까지는 통과하겠지만,
만약 최솟값이 8이 넘어갈 경우, 경우의 수는 어마무시 할 것..
package level3;
import java.util.*;
public class Solution_N으로표현 {
public static void main(String[] args) {
System.out.println(solution(4, 55));
}
static int calc(int o1, int o2, int c) {
if (c == 0) {
return o1 * o2;
} else if (c == 1) {
return o1 / o2;
} else if (c == 2) {
return o1 + o2;
} else return o1 - o2;
}
static public int solution(int N, int number) {
if (number == N) return 1;
List<List<Integer>> dp = new ArrayList<>();
int n = 0;
for (int i = 0; i <= 8; i++) {
dp.add(new ArrayList<>());
if(i==0) continue;
StringBuilder tmp = new StringBuilder("");
for(int j=0; j<i; j++) {
tmp.append(N);
}
n = Integer.parseInt(tmp.toString());
if(n==number) return i;
dp.get(i).add(n);
}
for (int i = 2; i <= 8; i++) {
for (int j = i - 1; j >= 0; j--) {
List<Integer> a1 = dp.get(i - j);
List<Integer> a2 = dp.get(j);
for (int a = 0; a < a1.size(); a++) {
for (int b = 0; b < a2.size(); b++) {
for (int c = 0; c < 5; c++) {
if(c==1 && a2.get(b)==0) continue;
n = calc(a1.get(a), a2.get(b), c);
if (n == number) return i;
dp.get(i).add(n);
}
}
}
}
}
return -1;
}
}
문제 출처 : Programmers