프로그래머스 42895 - N으로 표현
문제 링크
멍토 님의 IT블로그 게시글을 참고하였습니다.
생각 및 접근
- 문제 분야는 DP에 있었지만, 문제 접근은 DFS밖에 떠오르지 않았다.
- DFS로 접근하려고 했지만, dfs로 탐색해야 될 것이 너무 많았다. 예로 들어, 숫자를 합쳐서 계산하는 경우 모두를 dfs로 고려하려고 하니 쉽지 않았다.
- 구글링을 통해 멍토 님의 IT블로그를 참조하여 문제를 풀고, 이해할 수 있었다.
- DFS의 포인트는
- DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가 ,
- DFS의 초깃값을 어떻게 잡을 것인가 ,
- 언제 DFS를 멈추게 할 것인가 ,
- DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가
DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가
숫자를 몇 개 사용했는지 세는 int count와 count까지 오면서 계산한 int currentNumber를 넘긴다.
void dfs(int count, int currentNumber);
DFS의 초깃값을 어떻게 잡을 것인가
```
dfs(0, 0);
```
언제 DFS를 멈추게 할 것인가
count가 8보다 크면 답으로 인정하지 않고, 탐색을 멈춰야 한다.
if(count >= 9) return;
currentNumber == num이라면, 정답을 찾은 것이므로 탐색을 멈추고, answer를 업데이트한다.
if(currentNumber == num){
answer = min(answer, count);
return;
}
DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가
수많은 DFS를 반복문에 의해 처리된다.
int tempNumber = 0;
for(int i = 0; i + count < 9; i++){
tempNumber = tempNumber * 10 + n;
dfs(count + 1 + i, currentNumber + tempNumber);
dfs(count + 1 + i, currentNumber - tempNumber);
dfs(count + 1 + i, currentNumber * tempNumber);
dfs(count + 1 + i, currentNumber / tempNumber);
}
i의 역할
- n을 i번 붙여낸다. 즉, "nnn... n" (n이 i번) 라는 형태이다.
i + count < 9
- count가 9가 넘으면 더이상 DFS를 하지 않으니, 굳이 DFS를 하지 않고 for문 선에서 잘라낸다.
dfs(count + 1 + i, currentNumber ? tempNumber);
- n을 i번 붙인만큼, n을 i번 사용한 것이므로
count + 1 + i
- ?는 사칙연산
코드
#include <bits/stdc++.h>
using namespace std;
int n, num, answer = 9;
void dfs(int count, int currentNumber){
if(count >= 9) return;
if(currentNumber == num){
answer = min(answer, count);
return;
}
int tempNumber = 0;
for(int i = 0; i + count < 9; i++){
tempNumber = tempNumber * 10 + n;
dfs(count + 1 + i, currentNumber + tempNumber);
dfs(count + 1 + i, currentNumber - tempNumber);
dfs(count + 1 + i, currentNumber * tempNumber);
dfs(count + 1 + i, currentNumber / tempNumber);
}
}
int solution(int N, int number) {
n = N;
num = number;
dfs(0, 0);
if(answer == 9) return -1;
return answer;
}
채점 결과
