https://www.acmicpc.net/problem/21735
문제
눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 이고 위치 부터 위치 까지만 눈이 쌓여있다. 위치 에 눈이 만큼 쌓여있다. 대회 규칙은 해당 앞마당에서 초 동안 눈덩이를 굴려 눈사람을 만드는 것이다. 눈덩이의 시작 크기는 이다. 눈덩이의 시작 위치는 이다.
가장 큰 눈사람을 만들고 싶던 수수는 눈덩이를 굴리는 법을 연구했다. 눈덩이를 굴리는 방법에는 두 가지가 있다. 눈덩이를 굴리거나 던질 때 1초가 소모된다.
눈덩이를 현재 위치 +1칸으로 굴린다. 현재 칸의 위치를 라고 하면 눈덩이의 크기는 만큼 늘어난다.
눈덩이를 현재 위치 +2칸으로 던진다. 눈덩이가 착지하며 충격을 받아 눈덩이의 크기는 원래의 크기의 반으로 줄어들고 현재 칸의 위치를 라고 하면 눈덩이의 크기는 만큼 늘어난다. 이 때 소수점은 절사한다. 눈덩이를 던져 크기가 이 되어도 눈덩이는 사라지지 않는다.
눈덩이가 앞마당의 끝에 도달한 경우 남은 시간과 관계없이 눈덩이 굴리기는 끝이 난다. 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 구하는 프로그램을 작성해보자.
입력
첫째 줄에 공백을 기준으로 앞마당의 길이 (), 대회의 시간 ()이 주어진다.
둘째 줄에 길이가 인 수열 가 주어진다. ()
출력
첫째 줄에 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 출력한다.
두 가지 문제점만 빼고는 얼추 맞아서 그 두 가지는 주석에 달아놓았다
n, m = map(int, input().split())
lst = [0] + list(map(int, input().split())) # 눈덩이의 시작위치가 0인거 생각
ans = -1
def fun(idx, size, t):
global ans
if t > m: # t 전까지는 유효
return
if t <= m:
ans = max(size, ans)
if idx+1 <= n:
fun(idx+1, size+lst[idx+1], t+1)
if idx+2 <= n:
fun(idx+2, size//2 + lst[idx+2], t+1)
fun(0, 1, 0)
print(ans)