[백준] 18429번: 근손실 (파이썬)

✅문제: 18429번

18429번: 근손실

📌개념정리

(1) 백트래킹(Backtracking)

• 정의: 해결책에 대해 시도를 해보다가, 현재의 부분 해결책이 최종 해결책으로 이어지지 않을 것이라고 판단되면 이전 단계로 돌아가 다시 시도하는 기법
• 모든 가능한 경우의 수를 찾아보되, 각 단계에서 실패한 경우를 즉시 중단하고 다른 경로를 시도하는 방식임.

(2) 재귀 함수(Recursive Function)

• 정의: 함수가 자기 자신을 호출하여 문제를 해결하는 방식

# 재귀 함수 예
def factorial(n):
    if n == 0:
        return 1
    else: 
        return n * factorial(n-1)

📌문제풀이

N일 동안 매일 K의 근손실을 경험하며, 각 운동 키트의 추가 중량을 사용해 중량(500 이상)을 유지해야 함. 각 운동 키트는 하루에 하나만 사용 가능하고, 모든 키트를 사용하는 경우의 수를 구하는 문제임.

 

해당 문제는 각 운동 키트를 사용하여 근손실을 상쇄시키는 조합을 찾는 것이 중요함.

1. N일 동안 매일 운동 키트를 사용하면서 총 중량이 500 이상 유지되는지 확인
2. 각 일에 사용 가능한 키트를 순회하며 새로운 중량을 계산
3. 중량이 500 이하가 되지 않을 때만 다음 날짜로 넘어가서 탐색을 계속함
4. 모든 키트를 사용했을 때(재귀의 깊이가 N에 도달), 하나의 가능한 방법으로 카운트

def solution(N, K, kits, current_weight=500, day=0):
    if day == N:
        return 1
    
    count = 0
    for i in range(N):
        if kits[i] is not None:  # 사용하지 않은 운동 키트인 경우
            new_weight = current_weight + kits[i] - K
            if new_weight >= 500:  # 중량이 500 이상 유지되는 경우만 탐색
                saved_kit = kits[i]
                kits[i] = None  # 현재 운동 키트를 사용했음을 표시
                count += solution(N, K, kits, new_weight, day+1)
                kits[i] = saved_kit  # 다음 탐색을 위해 운동 키트를 복원
    return count

N, K = map(int, input().split())
kits = list(map(int, input().split()))

print(solution(N, K, kits))

1. 모든 N일 동안의 운동이 완료되었으면, 하나의 유효한 조합을 찾은 것이므로 1을 반환함.
2. 선택된 키트를 사용했을 때의 새로운 중량을 계산함. 새로운 중량은 `현재 중량 + 키트 중량 - 근손실`로 계산됨.
3. 새 중량이 500 이상인지 검사함. 만약 500 미만이라면, 유효하지 않으므로 더 이상 탐색하지 않음.
4. 유효한 경우에는 해당 키트를 사용했음을 표시하여 None으로 설정하고, 다음 날짜로 넘어가 재귀적으로 같은 검사를 수행함.
5. 재귀 호출이 끝나면 키트를 미사용 표시하여 복원하고 다른 가능성을 탐색함.

📌후기

• 처음에는 모든 가능한 키트의 사용 순서를 고려하여 잡할 것 같았지만, 재귀 함수를 이용하여 각 상황에서 유효한 선택만을 계속하게 해서 문제를 해결할 수 있었음.
• 문제의 조건을 이해하고 적절한 자료 구조와 알고리즘을 선택하는 것이 중요하다는 것을 다시 한번 느꼈음.