문제출처
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) / 55를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
제한사항
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
입출력 예
코드를 어디서 가지고 왔는데 어디서 가지고 온 지 몰라서 혹시 본인 코드다 생각되시면 댓글로 출처알려주세용😊
문제풀이
- 작은 문제로 큰 문제를 풀 수 있는 지 생각한다.
-> 여기서는 f(3) = f(1) @ f(2), f(2) @ f(1) 이런 형식으로 1에서 사칙연산된 값과 2에서 사칙연산된 값을 사칙연산하면 갯수 3개의 사칙연산 값을 구할 수 있다.
- 어떤걸 dp테이블에 넣을 지 생각한다.
-> 여기서는 계산되는 값 중 N이 되는 최솟값을 구하면 되기 때문에 각 index의 갯수 별 가능한 사칙연산을 모두 넣어준다.
- dp테이블은 가능한 길이만큼 설정한다.
-> 여기서는 최대가 9라고 하였기 때문에 길이를 9로 설정한다.
- 예외가 존재하는 지 생각한다.
-> 여기서는 N과 number가 같으면 1이 최솟값이기 때문에 if문으로 분기를 하고 else일 경우만 코드를 구현한다.
- 가능한 값 중 갯수만큼 붙여쓰는 값도 가능하기 때문에 사칙연산 구현 전 use배열에 반복되는 수의 값을 넣어준다.
- 1@3, 2@2, 3@1 형식대로 사칙연산을 구해야 하기 때문에 순차적으로 증가하는 값 순차적으로 감소하는 값의 사칙연산을 구현해준다.
- 최솟값을 구해야 하기 때문에 1부터 순차적으로 돌면서 number에 해당하는 숫자값이 있다면 리턴하고 종료한다.
다른사람 코드
function solution(N, number) {
var use = Array.from(new Array(9), () => new Set());
if(N==number) return 1;
else {
use.forEach((element, index) => {
if (index !== 0) element.add(Number(String(N).repeat(index)));
});
for(var i=1 ; i<=8 ; i++) {
for(var j=1 ; j<i ; j++) {
for(var first of use[j]) {
for(var second of use[i-j]) {
use[i].add(first+second);
use[i].add(first-second);
use[i].add(first*second);
use[i].add(first/second);
}
}
}
if(use[i].has(number)) return i;
}
return -1;
}
}점화식을 생각해 내는 것이 아직 익숙하지 않아 혼자 힘으로 풀지 못했는데 여러 dp를 풀어보면서 익숙해지도록 해야겠다.
TIL
- 처음 dp를 공부했을 때 dp테이블에 단순 숫자만 들어갈 수 있는 줄 알았는데 다양한 형식으로 dp테이블을 구성할 수 있다는 것을 알았다.
