[백준 알고리즘] 백준 21735번 눈덩이 굴리기 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 21735번 눈덩이 굴리기 파이썬(Python)

1) 문제번호 : 21735번

 

2) 문제 출처

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

21735번: 눈덩이 굴리기

 

2. 문제

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

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

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

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

 

3. 제약사항

4. 입력

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

둘째 줄에 길이가 N인 수열 a가 주어진다. (1≤ai≤1000000)

 

5. 출력

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

 

6. 풀이

- DP로 풀 수 있을것 같지만, DFS로 풀었다.

- 시간이 초과하면 리턴을 하고, 시간을 초과 안했으면 눈덩이 크기 비교를 한다.

- 그리고, 눈덩이 굴리기와 눈덩이 던지기에 따라 완전 탐색을 한다.

 

7. 소스 코드

import sys
input=sys.stdin.readline

# 앞마당의 길이 N, 대회의 시간 M
N, M = map(int, input().split())

# 첫 시작이 0부터 이므로 0을 추가하고 입력
A = [0] + list(map(int, input().split()))

def DFS(index, size, time):
    global ans #답

    #시간이 M을 초과하면 끝
    if time > M : return

    #시간을 초과하지 않으면 눈덩이 크기 비교해서 최대값 저장
    if time <= M :
        ans = max(ans, size)

    #눈덩이 굴리기
    if index <=N-1:
        DFS(index+1, size+A[index+1], time+1)

    #눈덩이 던지기
    if index <= N-2:
        #눈덩이 크기는 절반
        DFS(index+2, size//2 + A[index+2], time+1)

ans = -1

DFS(0,1,0)

print(ans)

---