프로그래머스 42895 - N으로 표현 (c++)

프로그래머스 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;
}

채점 결과