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

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

21735번: 눈덩이 굴리기

---

• 문제 : 

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

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

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

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

 

 

 

---

• 풀이 :

브루트 포스 문제이다. 재귀를 이용하여 모든 경우를 전부 탐색하고 가능한 경우만 정답에 넣어주고 max값을 찾는다.

 

 

 

---

• 소스코드 : 

 

import sys
 
input = sys.stdin.readline
 
def bf(curr,volume,cnt):
    if curr <= N-1:
        if cnt == M:
            ans.append(volume)
            return
    if curr == N-1:
        if cnt <= M:
            ans.append(volume)
            return
    if curr < N-1:
        bf(curr+1,volume+arr[curr+1],cnt+1)
    if curr < N-2:
        bf(curr+2,(volume//2)+arr[curr+2],cnt+1)
    return
 
if __name__ == "__main__":
    N,M = map(int,input().split())
    arr = list(map(int,input().split()))
    ans = []
    bf(-1,1,0)
    print(max(ans))