[Python/코테] 백준 21735 눈덩이 굴리기

21735 눈덩이 굴리기

알고리즘 설계

💡idea.

많은 경우의 수를 고려해서 합이 최대가 되는 경우를 구해야 하는데, 입력값이 제한을 넘지 않으므로 백트래킹을 사용한다.

🎲step.

1. 함수

백트래킹을 사용할 것이므로, 함수의 실행마다(즉 경우의 수마다) 총합을 구해준다.

최종적으로 가장 큰 값을 결과로 출력할 것이다.

snowball(t, i, value) #남은 시간 t, 이동한 현재 위치 i, 현재까지의 총합 value

2. Base condition

남은 시간이 0이거나 현재 위치가 끝일 때

t == 0 or i ==n

3. 재귀

합을 수행하고, 현재 위치에서 1번과 2번 이동 방법을 실행한다. 

if type == 1:

 

앞 1칸과 2칸의 요소 값의 비교 없이 연산이 끝나고 비교하는 이유는, 현재 위치에서 비교하면 결국 최대 값을 못 구할 수도 있기 때문이다. 끝 요소의 값이 큰데, 끝 요소에 도달하기 전에 당장의 큰 값만 찾다 시간이 종료되어 덧셈이 끝날 수도 있기 때문. 

알고리즘 구현

import sys

n, m = map(int, input().split())
yard = list(map(int, sys.stdin.readline().split()))
yard.insert(0, 0)
size = 1


def snowball(t, i, value):
    global size
    value += yard[i]

    if t == 0:      # 종료할 때가 되면, 최종 결과를 비교한다.
        # 어딘가에서 실행된 snowball함수가 더 큰 value값을 가지면 전역변수 size는 대체된다. -> 결국 모든 경우를 계산하고, 비교하는 셈이다.
        size = max(size, value)
        return

    if i == n:      # 시간이 다 되지 않아도, 위치가 끝나면 종료
        size = max(size, value)
        return

    if i+1 <= n:
        snowball(t-1, i+1, value)
    if i+2 <= n:
        snowball(t-1, i+2, value//2)


snowball(m, 0, 1)

print(size)

출처: https://phanre.tistory.com/12

나다어

• 백트래킹이란, 모든 경우의 수를 고려하는 것을 말한다. 가장 효율적인 방법보다, DFS를 기반으로 조건에 맞는지 확인해가며 전체를 순회하려는 목적임을 잊지 말자.