문제
https://school.programmers.co.kr/learn/courses/30/lessons/42895#
문제 설명
아래와 같이 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을 사용할 수 있는 최대 횟수는 8회이므로, 크기가 9인 배열 dp를 만들고, 0번째 배열은 비워둔다. 각 dp[i]는 N을 i번 사용해서 만들 수 있는 모든 숫자들의 집합을 저장하는 배열이다. dp 배열을 통해, i개의 N을 사용해서 만들 수 있는 값을 효율적으로 저장하고, 이를 바탕으로 더 큰 문제를 해결하는 구조를 생각했다.
초기 설정에서 dp[1]에는 N 자체를 넣고, dp[2]에는 N을 두 번 사용해서 만들 수 있는 값들을 계산한다. 예를 들어 N이 5라면, dp[2]에는 N/N, N+N, N*N, NN와 같은 값들이 들어간다. 그 후, 반복문을 통해 N을 3번부터 9번까지 사용할 때의 가능한 값들을 계산한다. 각 dp[i]에는 N을 i번 사용해서 연속한 숫자 (예: 555)를 먼저 넣고, 이전 단계에서 구한 dp[i-1] 값과 N을 조합하여 덧셈, 뺄셈, 곱셈, 나눗셈 등의 연산을 수행해 새로운 값을 만든다. 이 과정에서 구한 값이 목표 숫자인 number와 일치하면, 그때까지 사용한 N의 개수를 반환하여 최적의 답을 구한다.
이전에 계산된 작은 문제들의 결과를 조합하여 큰 문제를 해결하는 바텀업 방식의 동적 계획법을 사용해서 dp[i] = dp[i] + dp[i-1]의 아이디어를 사용했다. 만약 8번까지 연산해도 목표 숫자를 만들 수 없다면 -1을 반환한다.
코드 1 - 실패
function solution(N, number) {
let dp = new Array(9);
dp[1] = N;
dp[2] = [N/N,N+N,N*N,10*N+N];
for(let i = 3; i <=9 ; i++){
let num = parseInt(N.toString().repeat(i));
dp[i] = [num];
}
if(dp[1]==number){return 1}
if(dp[2].includes(number)){return 2}
let curUseCount = 3;
while(curUseCount<=9){
for(let i = 0; i<dp[curUseCount-1].length ; i++){
//곱하기 연산
let multi = N * dp[curUseCount-1][i];
if(multi == number){return curUseCount};
dp[curUseCount].push(multi);
//나누기 연산
let div = Math.floor(Math.max(N,dp[curUseCount-1][i])/Math.min(N,dp[curUseCount-1][i]));
if(div == number){return curUseCount};
dp[curUseCount].push(div);
//빼기 연산
let sub = Math.max(N,dp[curUseCount-1][i]) - Math.min(N,dp[curUseCount-1][i]);
if(sub == number){return curUseCount};
dp[curUseCount].push(sub);
//더하기 연산
let sum = N + dp[curUseCount-1][i];
if(sum == number){return curUseCount};
dp[curUseCount].push(sum);
}
curUseCount++;
if(dp[curUseCount].has(number)){return i}
}
return -1
}dp[i]는 단순히 dp[i-1]과 dp[1]을 더한 것이 아니라, i개의 N을 사용하는 모든 가능한 경우를 포괄해야 한다. 예를 들어, dp[4]를 구할 때 dp[2]와 dp[2]의 조합뿐만 아니라, dp[1]과 dp[3]의 조합도 고려해야 한다. 이렇게 dp[j]와 dp[i-j]의 모든 조합을 계산함으로써 dp[i]에서 나올 수 있는 모든 가능한 값을 찾을 수 있다.
이 방식은 부분 문제의 결과를 결합하여 더 큰 문제를 해결하는 동적 계획법의 기본 원리이다. 예를 들어 dp[4]를 만들 때, dp[2] + dp[2]로 만들 수 있는 값뿐만 아니라, dp[1] + dp[3] 또는 dp[3] + dp[1]의 조합으로도 새로운 값을 만들 수 있다.
코드 2 - 해결
function solution(N, number) {
// N과 number가 같으면 바로 1 반환
if (N === number) return 1;
let dp = Array.from({ length: 9 }, () => new Set());
dp[1].add(N); // dp[1]에는 N만 포함
// dp 집합을 2부터 8까지 생성
for (let i = 2; i <= 8; i++) {
// N을 i번 반복한 숫자를 추가 (예: 55, 555, ...)
dp[i].add(Number(N.toString().repeat(i)));
for (let j = 1; j < i; j++){
for(let num1 of dp[j]){
for(let num2 of dp[i-j]){
dp[i].add(num1+num2);
dp[i].add(num1-num2);
dp[i].add(Math.floor(num1/num2));
dp[i].add(num1*num2);
}
}
}
if(dp[i].has(number)){return i}
}
return -1
}복잡도 분석
- 시간 복잡도: 최악의 경우
O(n^3)(여기서n = 8), 따라서 약O(512)이다. - 공간 복잡도:
O(n)(여기서n = 8), 각dp[i]에 저장되는 값들의 수에 비례한다.
배운 점
DP에서는 작은 문제부터 해결해 나가며 점점 더 큰 문제를 해결하는 바텀업(Bottom-Up) 방식인 타뷸레이션(Tabulation)이 있다.
- 작은 문제부터 큰 문제로 확장:
- 먼저
dp[1]에는N하나만 사용했을 때 만들 수 있는 값을 넣고, dp[2]에는N을 두 번 사용했을 때 만들 수 있는 값들(예:N + N,N * N,N / N등)을 넣는다.- 그다음
dp[3]에는N을 세 번 사용한 값들, 즉dp[1]과dp[2]의 조합 등을 이용하여 가능한 숫자를 계산하고 넣는다.
- 먼저
- 점점 큰 문제로 나아감:
- 이후 계속해서
dp[i]를 만들 때, 이전에 구한dp[j]와dp[i-j]를 조합하여 가능한 값들을 차례대로dp[i]에 추가해나가며 이런 방식으로 점진적으로 큰 문제를 해결한다.
- 이후 계속해서
- 결과 도출:
- 목표 값인
number가 나오는 순간 그때까지 사용한N의 개수i를 반환한다. 만약dp[8]까지 계산해도number를 만들 수 없다면1을 반환한다.
- 목표 값인
