1. 문제에 대하여 📦
(1) 조건 분석 📊
N과 number가 주어질 때, N과 사칙연산만을 활용해 number를 나타내려고 한다.이때 최소로 드는 N의 개수는 몇 개인가? (다만, N의 개수는 8개를 넘을 수 없다.)
2. 코드가 나오기까지 🛠️
KEY WORD: DP그리디 알고리즘으로 매번 새로운 N을 기존 값에 사칙연산 해가는 풀이는 괄호를 나타낼 수 없기 때문에, 모든 경우의 수를 담을 수 없다.
여기서는 이전 풀이를 기억했다가 활용하는 기억하기 알고리즘인 DP를 써야한다.
다음과 같이 8개의 SET을 만든다. 각 SET은 N을 각각 n번 썼을 때 만들 수 있는 수의 집합이다.
N = 2 인 SET을 완성하려면?2 = 1+1 이기 때문에,
N=1 집합을 2개 이용하여 각 요소들에 대해서 사칙연산을 진행해야 한다.N = 3인 SET을 완성하려면?3 = 1+2 혹은 2+1이기 때문에
N=1과 N=2인 집합의 각 요소에 사칙연산을 진행해야 한다. 더하기와 곱하기는 각 항의 순서가 바뀌어도 되지만, 뺼셈과 나누기는 그렇지 않으므로 이를 주의하자.이런 식으로 현재 채우려는 SET을 이전에 계산이 완료된 SET들을 조합하여 채우는 방식으로 푼다. 이번 문제는 점화식은 필요없고,
이전 값 기억하기라는 DP의 특징을 가지고 있기에 DP 문제인 것 같다.(2) 주의점: N으로만 이루어진 숫자도 고려하기
N=5이면 5,55,555 ... 등 사칙연산없이 5로만 이루어진 숫자도 고려해야 한다.(1) 시간복잡도 분석 ⏳
M을 for문 당 연산이라 어림잡아 볼 때, 다음의 시간 복잡도가 든다.
- 현재 만드려는 N의 조합 중 하나 뽑기 (for문)
- 현재 만드려는 N의 조합 중 다른 하나 뽑기 (for문)
- 두 for문의 set 집합의 조합을 서로 사칙연산하기 (이중 for문)
1,2번은 거의 8 x 8 에 수렴하겠으나, 3번은 SET의 크기에 따라서 더 커질 수 있다.
3. 코드 🌐
(1) SUDO CODE 💬
1. 계층 별 집합 만들고, 각각 N으로만 이루어진 값 넣기 (ex: 5, 55, 555, ...) 2. N=2인 집합부터 시작해서 각 집합을 이전 계산한 집합을 조합하여 채우기 (1) 계산 과정에서 number와 동일한 값이 나오면 멈춰서 값 반환 3. 모든 집합을 계산할 때까지 답이 안 나오면 -1 출력하기
(2) JAVA CODE ☕
import java.util.*; class Solution { ArrayList<HashSet<Integer>> list = new ArrayList<>(); public int solution(int N, int number) { if(N == number) return 1; for(int i = 0; i <= 8; i++){ list.add(new HashSet<>()); } int cnt = 1; int t = N; while(cnt < 9){ list.get(cnt).add(t); t = t*10 + N; cnt++; }; for(int i = 2; i < 9; i++){ for(int j = 1; j <= (i/2.0); j++){ HashSet<Integer> target = list.get(i); HashSet<Integer> one = list.get(j); HashSet<Integer> ano = list.get(i-j); for(int a : one){ for(int b : ano){ target.add(a+b); target.add(a-b); target.add(b-a); target.add(a*b); if(b!=0) target.add(a/b); if(a!=0) target.add(b/a); } } if(target.contains(number)) return i; } } return -1; } }
4. 트러블 슈팅 or 배운 점📝
(1) DP로 풀 수 없는 이유
사칙연산에
()가 존재할 수 있기 떄문, 따라서 매번 새로운 단독 N을 기존 값에 사칙연산 해가면 괄호를 이용한 더 효율적인 식을 구할 수 없다.그리디 알고리즘으로 풀면 다음을 나타낼 수가 없다.
12 = (55/5) + (55/5)
