백준 18429번 - 근손실

근손실 문제 바로 가기

풀이 날짜: 2026-03-01

baekjoon 알고리즘 문제 풀이

풀이 코드


n,k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()

used = [False] * n

def dfs(power, depth):
    if power < 500:
        return 0

    if depth == n:
        return 1

    total = 0
    for i in range(n):
        if not used[i]:
            used[i] = True
            total += dfs(power + data[i] - k, depth + 1)
            used[i] = False
    return total

print(dfs(500,0))

문제 접근

이 문제는 N개의 운동 키트를 N일 동안 하루에 하나씩 순서대로 선택할 때, 매일 근력이 현재근력 + 키트증가량 - K로 변한다. 시작 근력은 500이고, 어떤 날이든 근력이 500 미만이 되면 그 순서는 실패 처리된다.

핵심 아이디어

왜 완전탐색(순열) + 백트래킹이 필요한가

키트의 선택 순서에 따라 중간 근력이 달라지고, 어떤 순서는 중간에 500 아래로 떨어져 탈락한다. 따라서 정렬이나 단순 반복으로는 경우를 셀 수 없고, 가능한 모든 순서를 시도해야 한다. N이 최대 8이라서 최악의 경우 8! = 40320 정도로 완전탐색이 가능하며, 중간에 실패하면 바로 잘라내는 가지치기(Pruning) 를 넣으면 더 빠르게 계산할 수 있다.

변수 설계

재귀 함수를 다음과 같이 설계했다.

현재 근력 power
지금까지 사용한 키트 개수 depth (“오늘이 몇 번째 날인지 = 몇 개 선택했는지”의미)
어떤 키트를 이미 썼는지 표시하는 uesd[]

내가 헷갈렸던 부분

depth를 왜 증가시키는지 이해가 안 됐다. 처음에는 depth가 무엇을 의미하는지 정확히 정리되지 않은 상태에서 코드를 작성했다. 따라서 재귀 호출 시 depth - 1로 잘못 넘기는 실수를 했다. 하지만 depth는 “현재까지 사용한 키트 개수(=날짜)”를 의미한다는 걸 정리한 뒤에야 이해가 됐다.
- 키트를 하나 선택하면 하루가 지나간 것
- 따라서 depth + 1이 되어야 함
- depth == n일 때가 모든 키트를 사용한 상태
왜 total += dfs(…) 인지 이해가 안 됐다. 처음에는 왜 +=로 더하는지 감이 오지 않았다. 하지만 이 문제는 “가능한 모든 순열의 개수”를 구하는 문제였다. 즉,
- 현재 선택 이후에 성공하는 경우의 수를 전부 더해야 현재 상태의 정답이 된다.

이 문제에서 기억해야 할 것

used[i] = False 의 필요성

키트 A를 선택하고 탐색을 끝낸 뒤
다시 다른 키트 B를 선택해야 하는데
A의 사용 표시가 그대로 남아 있으면 순열이 제대로 만들어지지 않는다. 즉, 선택 → 탐색 → 되돌리기 이 패턴이 백트래킹의 핵심이다.

Vienna sausage