(C++) - 백준(BOJ) 21735번 : 눈덩이 굴리기

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

21735번: 눈덩이 굴리기

백트래킹 문제였습니다.

 

풀이방법

 1. idx번째 눈덩이를 골랐을 때 대회시간과 고르기 직전의 size를 dfs함수의 인자로 설정합니다.

 

 2. idx번째 위치에서 다음 위치는 idx+1 또는 idx+2이므로 

max(idx + 1, cnt + 1, size + idx+1번째 눈덩이 크기, idx + 2, cnt + 1, size + idx+2번째 눈덩이 크기)가 idx번째 위치에서 가장 큰 눈덩이 크기가 됩니다. 이로써 모든 경우의 수를 확인할 수 있습니다. 대회시간의 최대값이 10이므로 O(2^10)안에 해결할 수 있습니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, m, a[101];

int bruteForce(int idx, int cnt, int size){
    if(cnt > m) return 0;
    if(cnt == m) return size;
    int ans = 0;
    ans = max(bruteForce(idx + 1, cnt + 1, size + a[idx+1]), bruteForce(idx + 2, cnt + 1, size/2 + a[idx+2]));
    return ans;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cout << bruteForce(0,0,1);
}