문제에서 주어진 정수를 연산을 하여 해답을 내놔야 하는 문제에서 DFS를 이용하면 풀리는 경우가 있다.
해당 문제는 주어진 정수 X를 입력 받고
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
이 세가지 연산을 이용해서 1을 만드는 것이다.
그 1을 만드는데 연산 횟수의 최솟값을 구하는 것이 문제
뭐가 문제여🤔
문제만 보면 간단히 보여서 그냥 while 써서 풀면 되는거 아니야?
했는데 반례를 보는 순간 결코 그런 단순한 문제가 아니라는걸 깨달았다.
(그런 문제라면 정답률이 30%대는 아니였겠지..)
반례가 무엇이냐면 X로 10이 주어진 경우다
10을 가지고 1로 만들기 위해 저 연산방법대로 한다면,
우선 연산 2번방법을 이용한다. 10은 2로 나누어 떨어진다. ( 연산 횟수 : 1 )
10이 5가 됐을텐데 1번,2번 연산에도 해당 안되니 -1을 해준다 ( 연산 횟수 : 2 )
4가 됐는데 2번연산을 두번해주면 1이 된다 ( 연산 횟수 : 4 )
자 근데, 연산 횟수가 최솟값이 아니기 때문에 오답이 뜬다!!
연산 횟수가 최솟값인 경우는 해당 경우이다.
10을 먼저 3번연산으로 9로 만들어 준다 ( 연산 횟수 : 1 )
3으로 두번 나누어 주어서 1로 만든다 ( 연산 횟수 : 3 )
연산횟수 4 보다 더 적은 연산 횟수가 등장 한다..
while로 해서는 택도 없는 것
연산순서에 우선순위를 정해버리는 것이기 때문에, 여기서는 우선순위 없이 다양한 방식으로 뻗어나갈수있는 방법을 생각 해나가야한다.
그것을 재귀, DFS로 해결해보았다.
Code⚙️
static int minCnt = Integer.MAX_VALUE;
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int X = input.nextInt();
DFS(X, 0);
System.out.print(minCnt);
}
static void DFS(int X, int cnt){
if(X==1){
if(minCnt > cnt)
minCnt = cnt;
return;
}
if (X % 3 == 0)
DFS(X / 3, cnt + 1);
if (X % 2 == 0)
DFS(X / 2, cnt + 1);
DFS(X - 1, cnt + 1);
}DFS를 이용해서 해결
DFS 재귀함수는 X가 1이되는 순간 종료를 시킨다
우선 순위에 상관 없이 X가 3 혹은 2로 나누어 떨어지면 cnt에 1을 추가해서
X를 새로운 값으로 갱신시키고 DFS를 다시 호출한다
그리고 X-1인 경우는 조건 해당없이 언제든 가능 한 것이기 때문에 X-1을 해서 DFS를 호출 해주었다.
뭐가 됐든, -1을 시작하고 연산 1번,2번을 진행하든 연산 1번,2번을 진행하고 -1을 해서 하든 재귀호출이기 때문에 우선순위에 종속되지않고 여러방법으로 연산들을 진행하기 때문에,
저절로 최솟값을 구하게 돼있다.
시간 초과의 이유📢📢📢
허허,, 근데 시간 초과가 나왔다.
뭣 때문이지? 생각해봤는데 솔직히 재귀를 저렇게 막 던지면
호출되는 상황이 너무 많아서 시간초과가 나는 것 외에는 생각이 들지 않았다.
재귀 호출이 많이 불리는 이유는 무엇인가...
연산을 호출할때 저렇게 하는 것을 고치는 건 아닌거같았다.
직관적으로 논리적으로도 호출을 저렇게 하는게 맞다고 생각 했기 때문
그렇다면 종료 조건이 아닐까? 종료조건을 더 추가해야하나?
수가 엄청 크다고 해보자.
분명히 진행하다 보면 최솟값이 결정된 경우가 있을 것이다.
DFS는 깊이 우선 탐색이다.
답이 결정돼있는 경우 혹은 이미 minCnt를 cnt가 넘은 경우에도
끝까지 연산을 들어가려고 할 것이다.
그런건 불필요한 연산이다. 시간 초과의 원인이 이 때문이 아닐까??
(생략...)
static void DFS(int X, int cnt){
//종료 조건 추가
if(cnt > minCnt)
return;
if(X==1){
if(minCnt > cnt)
minCnt = cnt;
return;
}
if (X % 3 == 0)
DFS(X / 3, cnt + 1);
if (X % 2 == 0)
DFS(X / 2, cnt + 1);
(생략...)해당 종료조건을 추가해주면 그러한 불필요한 연산을 없애 줄 것이라고 생각했다.
그래서 저 코드를 넣었더니..!!
해결..!
문제의 원인을 정확히 파악하면 간단한 코드 하나 넣는 것 만으로 문제를 해결 할 수 있다.
여러 코드 막 대입하면서 이거맞나 저거맞나 하는거보다 문제를 보며 정확히 뭐가 문제인지 뽑아내는 능력이 엄청 중요할 것이라는 생각이 든 날이었다.
