BOJ 21735 - 눈덩이 굴리기 (Python)

S3, 백트래킹

문제

눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다.
앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다.
위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 해당 앞마당에서 $M$초 동안 눈덩이를 굴려 눈사람을 만드는 것이다. 눈덩이의 시작 크기는 $1$이다. 눈덩이의 시작 위치는 $0$이다.

가장 큰 눈사람을 만들고 싶던 수수는 눈덩이를 굴리는 법을 연구했다. 눈덩이를 굴리는 방법에는 두 가지가 있다. 눈덩이를 굴리거나 던질 때 1초가 소모된다.

1. 눈덩이를 현재 위치 +1칸으로 굴린다. 현재 칸의 위치를 $i$라고 하면 눈덩이의 크기는 $a_{i+1}$ 만큼 늘어난다.
2. 눈덩이를 현재 위치 +2칸으로 던진다. 눈덩이가 착지하며 충격을 받아 눈덩이의 크기는 원래의 크기의 반으로 줄어들고 현재 칸의 위치를 $i$라고 하면 눈덩이의 크기는 $a_{i+2}$ 만큼 늘어난다. 이 때 소수점은 절사한다. 눈덩이를 던져 크기가 $0$이 되어도 눈덩이는 사라지지 않는다.

눈덩이가 앞마당의 끝에 도달한 경우 남은 시간과 관계없이 눈덩이 굴리기는 끝이 난다. 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 구하는 프로그램을 작성해보자.

풀이

• 생각보다 간단했는데, 백트랙킹 미숙함으로 실패했다.

from sys import stdin
n, m = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
res = 0
now = 1

def dfs(depth, idx, now):
    global res
    now += arr[idx]

    if depth == m:
        res = max(res, now)
        return
    if idx == n - 1:
        res = max(res, now)
        return

    if idx + 1 < n:
        dfs(depth + 1, idx + 1, now)

    if idx + 2 < n:
        dfs(depth + 1, idx + 2, now // 2)

dfs(1, 0, now)
if n > 1:
    dfs(1, 1, now//2)    # 바로 한칸 앞에 던지면서 시작

print(res)