문제
아래와 같이 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 |
풀이
DP(Dynamic Programming)을 적용하여 풀이할 수 있다. 왜냐하면 문제의 카테고리가 DP이기 때문이다(...).
실제 테스트에서는 카테고리가 이처럼 미리 정해서 주어지지 않기 때문에, 어떤 방식으로 풀이할 지 많은 고민이 필요하다.
특히 본인은 DP의 점화식을 찾아내기까지 굉장히 골머리를 앓는 편이라, 감이 잡히지 않는 문제는 일단 DP로 접근해보곤 한다...
본론으로 돌아와서, 해당 문제를 어떻게 DP를 이용해서 풀어낼 지 고민해보자.
사칙연산은 더하기 / 빼기 / 곱하기 / 나누기로 총 4개의 연산이 존재한다. 그리고 문제의 요구 조건에서 우리는 사용횟수가 8번이 넘어가는 경우에는 -1을 리턴해야 함을 알 수 있다.
그렇다면 크기가 8인 DP 배열을 하나 선언해두고, 각각의 위치(index)에 N이라는 숫자가 위치(index)만큼 사용하여 만든 결과를 저장하는 방식을 생각해봄직하다.
const DP = []; // 또는 const DP = new Array(N).fill(); 처럼 필요한 크기만큼 초기화하는 방식도 있다.
// DP[0] = N을 1번 사용하여 만들 수 있는 값들
// DP[1] = N을 2번 사용하여 만들 수 있는 값들
// ...
// DP[7] = N을 8번 사용하여 만들 수 있는 값들위와 같이 구성하는 경우 각각의 DP[index] 에는 여러 값들의 모음이 들어갈 것 이다. 예를 들어 N=5 일때 DP[1]에 들어갈 수 있는 수는, N + N = 10, N - N = 0, N * N = 25, N / N = 1 그리고 사칙연산 없이 N을 연달아배치한 수 55 총 5개가 가능하다. 즉 DP[1] = [ 10, 0, 25, 1, 55 ] 이와 같이 구성될 것 이다.
그런데 DP[2], 즉 5를 3번 사용하는 경우를 조금만 생각해보자. N * N / N = 5 이고, N - N + N = 5 이다. 여기서 우리는 사칙연산을 어떻게 조합하는가에 따라 중복된 결과가 나오는 것을 알 수 있다. 따라서 DP[0...7]은 중복된 값을 처리해 줄 수 있는 적절한 자료형을 사용해준다면 추후 불필요한 연산을 줄여 시간 복잡도에 도움이 될 것 이다. 우리는 JS를 사용하므로 new Set()을 사용하여 처리해주자.
for(let i = 0; i < 8; i++) {
DP[i] = new Set(); // 각각의 DP[index]에 Set을 넣어주자.
}본격적으로 점화식을 찾아 적용하기 전에, 점화식만큼이나 DP에 중요한 것이 DP를 초기화하는 과정이다.
위에서 잠깐 살펴봤듯이 우리는 무조건 사칙연산을 사용해야 하는 것이 아니다. N을 2번 사용한다면 55, 3번 사용한다면 555 와 같은 숫자 역시 포함된다. 즉 여기서 우리는 각 DP[index]의 초기값을 N을 각 index만큼 연달아 배치한 숫자들로 초기화할 수 있다. 위의 코드를 아래와 같이 수정해주도록 하자.
for(let i = 1; i <= 8; i++) { // i를 1부터 시작하여
const set = new Set(); // 반복시마다 Set을 하나씩 만들어서
DP.push(set.add(String(N).repeat(i) * 1)); // 해당 Set에 N을 i번 만큼 연달아 만든 수를 정수로 만들어 push
}
// 결과 : [ {5}, {55}, {555}, {5555}, {55555}, {555555}, {5555555}, {55555555} ]초기화까지 완료되었으니 본격적으로 점화식을 연구할 차례이다.
아까 위에서 N을 2번 사용했을때의 가능한 경우의 수는 총 5개로 { 10, 0, 25, 1, 55 } 로 Set에 들어가야 할 것 이다.
이때 각각의 숫자는 앞에서부터 더하기 / 빼기 / 곱하기 / 나누기 그리고 i만큼 연달아 배치하는 방식으로 구해주었다.
여기서 사칙연산의 피연산자로 쓰인 숫자들에 주목해보자. N + N / N - N / N * N ... 에서 N은 5를 의미한다.
그런데 우리는 5를 이미 앞에서 구해주었다. 즉 사전에 구한 값을 가지고 현재 구할 값에 이용하는 구조라고 볼 수 있다.
이 과정을 파악할 수 있다면 해당 문제가 DP 카테고리로 주어지지 않았더라도 진한 DP 스멜을 맡을 수 있다.
각설하고 다시 문제에 집중해서 이번엔 DP[2] (3번 사용하는 경우)는 어떻게 구성되는 지 살펴보자.
사전에 이미 구한 값을 활용한다는 것을 파악했기 때문에 DP[2]는 DP[1]에서 구한 값들을 이용해 사칙연산을 적용할 것 이다.
그런데 여기서 우리는 하나의 가능성을 더 고려해주어야 한다. DP[2]는 N을 3번 사용해서 만들 수 있는 값의 집합이다. 그런데 DP[1]은 N을 2번 사용해 만든 값의 집합이다. 즉 여기서 N을 1번 더 사용해야 하는데, 우리는 N을 1번 사용한 값의 집합을 미리 구해놓았다. 따라서 다음이 성립한다.
DP[2] = DP[0]의 각각의 값 (더하기 / 빼기 / 곱하기 / 나누기) DP[1]의 각각의 값 + N을 3번 연달아 사용한 값
이때 N을 연달하 사용한 값은 초기화 때 미리 구해주었으므로 반복문을 돌릴 때 굳이 다시 계산해주지 않아도 된다.
만약 DP[3] (4번 사용하는 경우)는 다음과 같을 것이다.
- DP[0] (1번 사용) <사칙연산> DP[2] (3번 사용)
- DP[1] (2번 사용) <사칙연산> DP[1] (2번 사용)
하지만 마지막으로 주의해야 할 사항이 있다. 더하기와 곱하기 같은 경우는 해당되지 않지만 빼기와 나누기의 경우에는 교환법칙이 성립하지 않는다. 즉 빼기와 나누기의 경우엔 똑같이 4번을 사용하더라도, DP[0] - DP[2]의 결과와 DP[2] - DP[0]의 결과가 서로 다를 수 있는 것이다. 따라서 아래 3번까지 모두 반복문을 돌면서 계산을 해주어야 한다.
- DP[2] (3번 사용) <사칙연산> DP[0] (1번 사용)
따라서 N을 2번 사용하는 위의 경우에서도 다음과 같이 진행되어야 한다.
1. DP[2] = DP[0] <사칙연산> DP[1]
2. DP[2] = DP[1] <사칙연산> DP[0]
해당 점화식을 만드는 반복문은 다음과 같다.
i = 3 (4번 사용하는 경우) 일 때, 구해야 하는 조합이 위의 예시와 같음을 기억하자.
DP[3] = { DP[0] <사칙연산> DP[2] } U { DP[1] <사칙연산> DP[1] } U { DP[2] <사칙연산> DP[0] }
즉 j의 값은 0부터 시작하여 최고점 i - j - 1을 찍고 다시 0으로 내려가는 것을 확인할 수 있다.
for(let i = 0; i < 8; i++) {
for(let j = 0; j < i; j++) {
...DP[j] 부터 DP[i-j-1] 까지 돌면서 각각 사칙연산
}
}이렇게 반복문을 돌면서 만약 해당하는 수가 발견되는 경우엔 반복을 중단하고 사용횟수를 반환하고,
끝까지 돌았음에도 찾지 못했다면 -1을 반환하도록 구현하면 되겠다.
코드
function solution(N, number) {
let answer = -1;
const DP = [];
for(let i = 1; i <= 8; i++) {
const set = new Set();
DP.push(set.add(String(N).repeat(i) * 1));
}
for(let i = 0; i < 8; i++) { // N을 1번 사용하는 경우부터 조사
for(let j = 0; j < i; j++) { // DP[0] ~ DP[i - j - 1] 까지 탐색
for(const v1 of DP[j]) { // DP[j]는 항상 DP[0]부터 시작
for(const v2 of DP[i-j-1]) { // v1과 v2는 해당 인덱스에 담긴 집합들 각각의 값을 의미
cal(DP, v1, v2);
}
}
}
if(DP[i].has(number) {
answer = i+1;
break;
}
}
return answer;
}
const add = (a, b) => {
return a + b;
}
const sub = (a, b) => {
return a - b;
}
const mul = (a, b) => {
return a * b;
}
const div = (a, b) => {
if(b === 0) return 0;
return Math.floor(a/b);
}
const addDP = (DP, res) => {
DP.add(res);
}
const cal = (DP, a, b) => {
addDP(DP, add(a, b));
addDP(DP, sub(a, b));
addDP(DP, mul(a, b));
addDP(DP, div(a, b));
}사칙연산을 모듈식으로 따로 분리해 함수로 작성했는데,
다른 사람들의 풀이를 보아하니 굳이 코드양만 많아진 것 같다.
출처
