[백준 | 실버3] 21735번: 눈덩이 굴리기(백트랙킹, 완전탐색, 인덱스만큼 이동)

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

문제

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

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

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

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

입력

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

둘째 줄에 길이가 N$N$인 수열 a$a$가 주어진다. (1≤ai≤1000000$1 \leq a_i \leq 1\,000\,000$)

출력

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

예제 입력 1 복사

10 5
1 3 4 5 6 7 8 10 12 14

예제 출력 1 복사

28

 

문제풀이

앞마당의 길이는 N이
위치 1부터 위치 N까지만 눈이 쌓여있다.
위치 i에 눈이 a[i]만큼 쌓여있다.
해당 앞마당에서 M초 동안 눈덩이를 굴려 눈사람을 만드는 것
눈덩이를 굴리거나 던질 때 1초가 소모
눈덩이의 시작 크기는 1
눈덩이의 시작 위치는 0

방법1
눈덩이를 현재 위치 +1칸 굴림 -> a[i] + 1 만큼 커짐
방법2
눈덩이를 현재 위치 +2 던짐 -> (원래 크기 // 2) + (a[i]+2)

 

문제해결

n개에서 m초가 될때 까지 DFS
0번째 칸에서 시작해서 한 턴에 한칸, 혹은 두 칸을 가는 경우에 대해 m번 째 턴까지 모든 경우를 확인

n, minutes = map(int, input().split())             #앞마당 길이 n, 대회사긴 minutes
num_list = [0] + list(map(int, input().split()))
max = -1

def DFS(index, size, time) :
    global max

    #시간이 m 초과하면 종료
    if time > minutes :           
        return
    #시간을 초과하지 않으면 눈덩이 크기 비교해서 최대값 갱신
    if time <= minutes :          
        if size > max :
            max = size

    #눈덩이 굴리기(a[i] + 1)
    if index <= n-1 :
        #다음 인덱스+1, 키운 사이즈, 시간+1
        DFS(index+1, size+num_list[index+1], time+1)
    
    #눈덩이 던지기 : (원래 크기 // 2) + (a[i]+2)
    if index <= n-2 :
        #다음 인덱스+2, 키운 사이즈, 시간+1
        DFS(index+2, (size//2) + num_list[index+2], time+1)

DFS(0, 1, 0)        #눈덩이의 시작 위치는 0, 시작크기는 1, 시작 시간은 0
print(max)