📂 문제 설명
아래와 같이 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번만 사용하여 표현할 수 있습니다.
📂아이디어 및 알고리즘(문제 풀이)
- N을 최소한으로 사용하여 number를 나타내면 되는 문제이다.
- N으로 나타내는 방법에는 연산하여 구하는 방법과 N을 중복 사용하여 구할수도 있다.
- 이 문제는 DFS를 이용하여 N의 사용 횟수에 따라 값을 비교해 가며 최솟값을 찾으면 된다.
- DFS에는 사용하고자 하는 n, 사용 갯수를 나타내는 UsingCount, 만들어진 num, 구하고자 하는 number 를 인자로 넣어준다
- UsingCount가 8보다 크게되면 강제 종료를 시키고
- num == number이면 UsingCount가 answer보다 작으면 갱신시켜준다.
- for문에서는 newnum이란 수를 이용하고 i번은 횟 수를 의미하며 N을 몇번 중복 사용하여 연산을 해줄지를 구하여 DFS로 넘겨준다.
- ex) N=5 이고 i=0일때 5 하나만 이용하여 연산이 가능하고 i=1이면 55로하여 연산이 가능하도록 도와준다.
- 이런식으로 DFS를 돌며 최솟값을 찾아 줄 수 있게된다.
- usingCount + (1+i)의 의미는 newnum을 포함시켰을때의 N사용 횟수이다.
📂소스코드
class Solution {
static int answer= -1;
public int solution(int N, int number) {
DFS(N,0,0,number,"");
return answer;
}
//DFS로 풀기
public static void DFS(int n , int UsingCount, int num, int number, String s) {
if(UsingCount > 8) {
return;
}
if(num == number) {
if(UsingCount < answer || answer == -1) {
answer = UsingCount;
}
return;
}
int newnum=0;
for(int i=0;i<8-UsingCount;i++) {
newnum =newnum*10 + n;
DFS(n, UsingCount+1+i, num + newnum, number, s+"+");
DFS(n, UsingCount+1+i, num - newnum, number, s+"-");
DFS(n, UsingCount+1+i, num * newnum, number, s+"*");
DFS(n, UsingCount+1+i, num / newnum, number, s+"/");
}
}
}
📂후 기
보기에 간단해 보인 문제인데 막상 풀어보니 어려웠다... 특히 중복사용하여 연산을 해나가야 한다는 아이디어가 떠오르지 않아서 구글링을 하여 참고하여 풀게 되었다. 문제를 직관적으로 보고 최대한 간결하게 생각하여 풀고 싶은데 잘 되지가 않는다ㅠㅠ
'알고리즘(Java) > programmers' 카테고리의 다른 글
[JAVA] 등굣길 (코딩테스트 고득점 Kit [ 동적계획법(DP)]) - LEVEL3 (0) | 2020.10.22 |
---|---|
[JAVA] 정수 삼각형 (코딩테스트 고득점 Kit [ 동적계획법(DP)]) - LEVEL3 (0) | 2020.10.22 |
[JAVA] 단속 카메라 (코딩테스트 고득점 Kit [ Greedy(탐욕법) ]) - LEVEL3 (0) | 2020.10.21 |
[JAVA] 섬 연결하기 (코딩테스트 고득점 Kit [ Greedy(탐욕법) ]) - LEVEL3 (0) | 2020.10.21 |
[JAVA] 구명보트 (코딩테스트 고득점 Kit [ Greedy(탐욕법) ]) - LEVEL2 (0) | 2020.10.10 |