[백준] 21735번: 눈덩이 굴리기 (python)

21735번: 눈덩이 굴리기

---

문제 )

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

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

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

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

 

 

입력 :

첫째 줄에 공백을 기준으로 앞마당의 길이 N(1 <= N <= 100), 대회의 시간 (1 <= M <= 10)이 주어진다.

둘째 줄에 길이가 N인 수열 a가 주어진다 ( 1 <= ai < 1,000,000)

 

 

출력 :

첫째 줄에 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 출력한다.

 

 

 

풀이)

크게 어려울 게 없는 문제였는데,,,

초반에 [0]을 넣는 것과 

중간에 리스트의 모습을 본다고 print를 하나 넣어놓은게 계속된 오답을 만들어 냈다..

def recur(cur, snow, i):
    global answer
 
    # 시간이 끝났거나, 앞마당을 벗어나면 끝
    if cur == m or i > n:
        answer = max(answer, snow)
        return
 
    # 눈덩이를 굴릴 때
    # 시간 +1, 다음 눈송이 붙이기, 위치 옮기기
    recur(cur + 1, snow + li[i + 1], i + 1)
 
    # 눈덩이를 던질 경우
    # 시간 +1, 다음 눈송이 붙이기, 위치 옮기기
    recur(cur + 1, (snow // 2) + li[i + 2], i + 2)
 
n, m = map(int, input().split())
li = [0] + list(map(int, input().split())) + [0] * 4
answer = -1
recur(0, 1, 0)
print(answer)

---

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

21735번: 눈덩이 굴리기