[BOJ] 눈덩이 굴리기_21735 C++ 풀이

문제

눈덩이 굴리기

• 눈덩이를 현재 위치 +1칸으로 굴린다. 현재 칸의 위치를 i라고 하면 눈덩이의 크기는 ai+1만큼 늘어난다

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

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

접근방법

처음에는 DP로 접근하였으나 ai 형식의 n-튜플 형식이고 입력 데이터의 크기도 크지 않아 백트래킹으로 해결해 보았다.

가능한 모든 경우의 수를 고려한 다음, 눈덩이의 크기가 최대인 경우를 값으로 받아 출력해 주었다.

구현

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int N, M;
int t = 0, snow = 1, ans = 0;
int a[101];

void backTrack(int pos, int snow, int t)
{
    if(t >= M) 
    {
        ans = max(ans,snow);
        return;
    }

    backTrack(pos+1, snow + a[pos+1], t + 1 );
    backTrack(pos+2, snow/2 + a[pos+2], t + 1);
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0);
    memset(a, 0, sizeof(int));
    cin>>N>>M;
    
    for(int i=1; i<=N; i++) cin>>a[i];

    backTrack(0, snow, t);

    cout<<ans<<'\n';
    return 0;
}