[PS] 타겟 넘버

 

프로그래머스

문제

입력받은 숫자를 더하거나 빼서 목표 숫자 만들기

 

풀이

이 문제는 DFS/BFS 분류에 해당하는 문제다

사실 이 알고리즘 분류 몰랐으면 풀기 좀 어려웠을 것 같긴 한데..

목표 숫자를 찾는다는 것을 중점으로 생각해보니 그래도 잘 풀렸다.

---

1. DFS 함수

[1, 1, 1, 1, 1]

과 같은 인접 리스트를 입력받았다고 생각해보자.

이때, 현재 방문한 수를 (1) 더하거나 (2) 빼거나 둘 중 하나를 할 수 있다.

 

그런데, 더하거나 빼거나 둘 중 하나를 해서 마지막 인덱스까지 계산한 결과가 target인지 확인해야하므로, 끝까지 계산한 시점에 카운트해야한다.

따라서 DFS 재귀 방식으로 구현하면서 연산 결과를 파라미터로 가져오고 target과 동일하다면 횟수를 카운트하면 된다.

 

즉 우리에게 필요한 정보는

(1) 현재 수에서 numbers[index]를 더하거나 뺀 결과

(2) 현재 수의 인덱스

이렇게 두 개로 생각할 수 있다.

void DFS (int result, vector<int> numbers, int target, int index){}

따라서 DFS 함수는 이렇게 세울 수 있다.

함수 내부 구문에서 result에 numbers[index] 수를 더하는 경우, 뺀 경우를 둘 다 재귀로 호출하면 된다.

 

2. 종료, 카운트 조건

1. 현재 인덱스가 마지막 인덱스라면

현재 index가 마지막 index라면, 즉 다시말해 index가 numbes.size()와 동일한지 확인한다.

2. 목표 숫자라면

현재까지 더하거나, 빼서 구해온 수 (result)가 목표 숫자(target)라면 카운트 횟수를 1회 더한다.

if (index == numbers.size()){
        if (result == target) {
            cnt++;
        }
        return;
    }

 

 

코드

#include <string>
#include <vector>

using namespace std;

int cnt = 0;

void dfs (int result, vector<int> numbers, int target, int index){
    if (index == numbers.size()){
        if (result == target) {
            cnt++;
        }
        return;
    }
    
    dfs(result + numbers[index], numbers, target, index + 1);
    dfs(result - numbers[index], numbers, target, index + 1);
}

int solution(vector<int> numbers, int target) {
    dfs(0, numbers, target, 0);
    
    return cnt;
}

 

 

회고

모든 경우를 다 탐색해야 한다면 DFS가 유리하다!

이걸 알고 풀면 생각보다 쉬운 문제였다