백준 20167 꿈틀꿈틀 호석 애벌레 (기능성)

dasd412·2022년 9월 6일

코딩 테스트

목록 보기

61/71

문제 설명

꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 수 있다. 또한 매초 1 만큼 오른쪽으로 무조건 진행한다.

호석 애벌레는 i 번째 먹이가 맛있을수록 높은 만족도를 얻는다. 호석 애벌레는 절제라는 것을 모르는 욕심쟁이기 때문에 한번 먹이를 먹기 시작하면 연속적으로 계속 먹어야 하며, 누적된 만족도가 최소 만족도 K 이상이 되거나 더 이상 먹을 먹이가 없을 때에 연속적으로 먹는 것을 멈춘다. 만약 최소 만족도 이상이 되면 K 를 초과한 만족도만큼 탈피 에너지를 축적한다. 직후에 호석 애벌레의 만족도는 다시 0 이 되고 먹이를 먹을 수 있게 된다. 나뭇가지를 전부 통과했을 때에 소화를 다 못 했을 경우에도 탈피 에너지는 최소 만족도를 넘기는 순간 이미 축적한 것으로 생각하자.

매초마다 호석 애벌레는 오른쪽으로 이동하면서 먹이를 지나치거나 먹기 시작할 수 있다. 먹기 시작하면 만족도가 채워질때까지 먹게 될것이다. 어떤 먹이들을 대해 먹어야 축적된 탈피 에너지가 최대가 될 수 있을까?

입력 조건

첫번째 줄에 먹이 개수 N, 최소 만족도 K 가 공백으로 주어진다.

두번째 줄에는 1 번부터 N 번 먹이의 만족도가 순서대로 주어진다.

출력 조건

축적된 탈피 에너지의 최댓값을 구하라. 만약 탈피를 한 번도 할 수 없다면 0을 출력한다.

제한 조건

1 ≤ N ≤ 20, N 은 정수이다.
1 ≤ K ≤ 100, K 는 정수이다.
0 ≤ 각 먹이의 만족도 ≤ 100, 모든 만족도는 정수이다.

전체 코드

import sys

sys.setrecursionlimit(10 ** 5)

n, k = list(map(int, sys.stdin.readline().split()))
arr = list(map(int, sys.stdin.readline().split()))

answer = 0


# 이 문제의 경우 n이 최대 20이므로 재귀를 활용할 수 있다.
# 연속으로 먹어야 한다는 조건은 일종의 백트래킹 가지치기라고 볼 수 있다.
def back_tracking(array: list[int], index: int, current_satisfaction, current_energy):
    global answer, k
    if index >= len(array):
        answer = max(answer, current_energy)
        return
    else:
        next_satisfaction = current_satisfaction + array[index]
        # 최소 만족도가 넘을 경우 탈피 에너지 축적하는 분기
        if next_satisfaction >= k:
            next_energy = current_energy + (next_satisfaction - k)
            back_tracking(array, index + 1, 0, next_energy)
        # 넘지 못하면 그냥 만족도만 높임
        else:
            back_tracking(array, index + 1, next_satisfaction, current_energy)
        
        # 아예 해당 구간 선택하지 않는 분기
        # 문제 조건에서 애벌레는 '연속적으로' 먹을 때만 만족도가 누적된다.
        back_tracking(array, index + 1, 0, current_energy)


back_tracking(arr, index=0, current_satisfaction=0, current_energy=0)
print(answer)