프로그래머스 43165 - 타겟 넘버 (Lv.5)

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

// 프로그래머스 43165 - 타겟 넘버 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/43165
// (같은 이진 분기 골격: 백준 15651 N과 M (3) — 매 자리에서 선택지가 고정된 중복 순열)

// 문제 설명
// n 개의 음이 아닌 정수가 순서대로 주어진다. 순서를 바꾸지 않고 각 수에 + 또는 - 를 붙여
// 더했을 때 타겟 넘버를 만드는 방법의 수를 반환하라.

// 제약 조건
// 2 <= numbers 길이 <= 20
// 1 <= numbers 의 원소 <= 50 (자연수)
// 1 <= target <= 1,000 (자연수)

// Example
// Input : numbers = [1, 1, 1, 1, 1], target = 3
// Output: 5        (-1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1)
//
// Input : numbers = [4, 1, 2, 1], target = 4
// Output: 2        (+4+1-2+1, +4-1+2-1)

// 접근 — 자리마다 + / - 두 갈래로 내려가는 DFS
//
// [1단계 — 선택지가 원소가 아니라 부호다]
// 순서를 바꿀 수 없다는 조건이 이 문제를 순열에서 떼어낸다. 고를 것은 "어떤 수를 쓸까"가
// 아니라 "i 번째 수의 부호를 무엇으로 할까"이고, 선택지는 항상 두 개로 고정이다.
// 그래서 visited 배열이 필요 없다 — 각 자리를 정확히 한 번만 지나가므로 상태 오염이 없고,
// 되돌리기(빼고)도 필요 없다. 누적합을 인수로 넘기면 되돌림이 호출 스택에 흡수된다.
//
// [2단계 — 완전탐색으로 갈 수 있는 근거는 제약]
// 잎의 개수는 2^n, n <= 20 이므로 최악 2^20 = 1,048,576 가지. 브루트포스가 그대로 통한다.
//
// [3단계 — 왜 BFS가 아니라 DFS인가 (자료구조 선택 근거)]
// 부호 조합을 큐로 넓혀 나가는 BFS도 답은 같지만, 마지막 레벨에서 큐가 2^20 개의
// 부분합을 동시에 들고 있어야 한다. DFS는 재귀 깊이가 n = 20 으로 고정이라 상태가 한 줄뿐이다.
// 최단 거리를 묻지 않고 "끝까지 내려간 경우의 수"만 세는 문제라 넓이를 유지할 이유가 없다.
//
// [4단계 — 세는 문제이므로 int 반환 dfs]
// 전역 ans++ 대신 실패 0 / 성공 1 을 반환하고, 중간 노드는 두 자식의 반환값을 그대로 더한다.
// 잎에서만 판정하므로 조건 분기가 함수 진입부 한 줄로 끝난다.
//
// 시간 O(2^n) 최악 약 105만, 공간 O(n) (재귀 깊이 20)

#include <vector>

using namespace std;

int n, t;                            // 전역 선언 — 재귀 인수를 depth·sum 두 개로 줄인다
vector<int> v;

int dfs(int depth, int sum)
{
    if (depth == n) return sum == t ? 1 : 0;   // 모든 부호를 정한 잎에서만 판정

    return dfs(depth + 1, sum + v[depth])      // + 갈래
         + dfs(depth + 1, sum - v[depth]);     // - 갈래 (누적합을 넘기므로 되돌리기가 없다)
}

int solution(vector<int> numbers, int target)
{
    n = (int)numbers.size();
    t = target;
    v = numbers;

    return dfs(0, 0);
}

정리

• “순서를 바꾸지 않는다”는 한 줄이 유형을 결정한다. 이 조건 때문에 고를 것이 원소가 아니라 i번째 수의 부호가 되고, 선택지는 자리마다 정확히 두 개로 고정된다. 그래서 순열 백트래킹의 장비 두 개가 통째로 사라진다 — 각 자리를 한 번만 지나가므로 visited가 필요 없고, 누적합을 인수로 넘기므로 되돌리기(빼고)도 필요 없다. 넣고/빼고 대칭은 전역·배열 상태를 고칠 때만 필요하고, 인수로 넘기는 값은 호출 스택이 알아서 복원한다.
• 완전탐색으로 가는 근거는 잎의 개수다. 2^20 = 1,048,576이라 100만 연산 수준이고, 잎에서 비교 한 번씩만 하므로 그대로 통과한다. n이 40쯤이면 같은 코드가 1조가 되어 무너지는데, 제약을 읽고 유형을 고정하는 습관이 여기서 값을 한다.
• DFS와 BFS의 차이가 답이 아니라 메모리에서 난다. 부호 조합을 레벨별로 넓히는 BFS도 답은 같지만 마지막 레벨에서 큐가 2^20개의 부분합을 동시에 들어야 한다. DFS는 재귀 깊이가 20으로 고정이라 상태가 한 줄뿐이다. 최단 거리를 묻지 않고 경우의 수만 세는 문제는 넓이를 유지할 이유가 없다 — 1697 숨바꼭질처럼 최소 횟수를 묻는 문제와 갈리는 지점.
• 세는 문제이므로 int dfs() 반환. 전역 ans++ 대신 잎에서 성공 1 / 실패 0을 반환하고 중간 노드는 두 자식의 반환값을 더하기만 한다. 판정이 함수 진입부 한 줄로 모여서 solution이 여러 번 호출돼도 초기화할 전역 카운터가 없다.
• 본문의 “음이 아닌 정수”와 제약의 “1 이상”이 어긋나는데, 제약 쪽이 함정을 없애 준다. 만약 0이 들어올 수 있으면 +0과 -0이 같은 식을 두 번 세어 답이 부풀지만, 원소가 1~50 자연수로 보장되므로 두 갈래가 항상 서로 다른 식이 되어 중복 계산이 없다. 부호 분기 문제에서 0은 늘 확인해야 하는 축이다. 커리큘럼 94번.
• 더 줄이려면 두 갈래가 있다. 남은 수들의 합 rest를 미리 구해 |target - sum| > rest인 순간 그 아래 잎을 전부 잘라내는 가지치기, 또는 부분합 범위가 -1000 ~ 1000으로 좁으니 dp[자리][부분합] 카운팅으로 O(n x S)까지 내리는 방법. 다만 2^20이 이미 통과 범위라 여기서는 골격이 드러나는 완전탐색을 그대로 뒀다.
• 검증: 예제 2개(5, 2)와 경계 케이스 — 최소 길이에서 유일 해([1,1] → 2 = 1), 해가 없는 입력([1,1] → 1 = 0), 최대 입력 20개 전부 50에 target = 1000(전부 +인 1가지) 통과 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — “순서를 바꾸지 않는다”가 유형을 정한다. 고를 것은 원소가 아니라 자리별 부호이고 선택지가 항상 둘로 고정되므로 visited도 되돌리기도 필요 없다(누적합을 인수로 넘기면 호출 스택이 복원한다). 잎이 2^20 = 약 105만이라 완전탐색이 그대로 통하고, 같은 탐색을 BFS로 하면 마지막 레벨에서 큐가 2^20개의 부분합을 들어야 하므로 경우의 수만 세는 문제에는 깊이 20이 고정인 DFS가 맞다.