[프로그래머스 Level 2] 타겟 넘버

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

 

풀이

• n개의 음이 아는 정수들을 더하거나 빼서 타겟 넘버를 만들어야 한다.
• 순서를 서로 바꾸지 않기 때문에 같은 값이라도 다른 숫자로 취급한다.

 

n개의 정수들을 모두 계산해야 하기 때문에 DFS로 모든 경우의 수를 탐색하는 방향으로 문제에 접근하였다.

 

먼저 DFS의 재귀 탈출 조건을 생각하였다. n개의 정수를 모두 계산해야 하니까 배열의 길이를 탈출 조건으로 걸어 DFS의 깊이가 같아지는 순간 return 해주기로 하였다.

이때, 타겟과 현재 계산 결과를 비교하여 같다면 count를 1 늘려주었다.

 

if(depth == numbers.length){
    if(sum == target){
        count++;
    }
    return;
}

 

 

더하기와 빼기 두가지 연산이 가능하므로 계산된 값에서 현재 숫자를 더하거나 빼주었고 depth는 1을 더한 값으로 가지를 늘려주었다.

 

int plus = sum + numbers[depth];
int minus = sum - numbers[depth];

dfs(depth + 1, plus, numbers, target);
dfs(depth + 1, minus, numbers, target);

 

 

 

전체 코드 (Java)

import java.util.*;

class Solution {
    int count = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(0, 0, numbers, target);
        
        return count;
    }
    
    public void dfs(int depth, int sum, int[] numbers, int target){
        if(depth == numbers.length){
            if(sum == target){
                count++;
            }
            return;
        }
        
        int plus = sum + numbers[depth];
        int minus = sum - numbers[depth];
        
        dfs(depth + 1, plus, numbers, target);
        dfs(depth + 1, minus, numbers, target);
    }
}

 

 

후기

DFS의 재귀 탈출 조건과 전달 인자에 대해 생각해 볼 수 있는 간단하지만 좋은 문제였던 것 같다.