[Python/파이썬] - 백준(BOJ) 21735번 : 눈덩이 굴리기

https://www.acmicpc.net/problem/21735

21735번: 눈덩이 굴리기

 

간단한 브루트 포스 문제.

시작점은 0이므로 다음 눈덩이의 위치는 1, 2 두가지가 가능하다.

만약 앞마당의 길이가 2가 되지 않는다면 2는 생략한다.

0에서 1로 가게되면 그대로 눈덩이의 크기를 전달하고

0에서 2로 가게되면 눈덩이의 크기를 절반을 만들어서 함수에 넣는다.

이후 1에서는 2, 3 / 2에서는 3, 4 / ... / n-1, n 까지 도달하도록 재귀함수를 작성한다.

시간이 제한시간과 같아지거나 인덱스가 마당의 끝까지 도달하면 종료한다.

 

 

def Back(time, index, value):
    global answer
    value += arr[index]
    if time == m:
        answer = max(answer, value)
        return
    if index == n-1:
        answer = max(answer,value)
        return
    if index+1 < n:
        Back(time+1, index+1, value)
    if index+2 < n:
        Back(time+1, index+2, value//2)

n, m = map(int,input().split())
arr = list(map(int,input().split()))
answer = 0
Back(1, 0, 1)
if n > 1:
    Back(1, 1, 0)
print(answer)