[백준] 21735번 눈덩이 굴리기

 

처음에 문제를 보고 DP를 생각했으나 앞마당 끝에 도달하지 않고 대회 시간이 모두 경과됐을 경우 또한 고려해야 하여 재귀로 모든 경우의 수를 확인했다.

 

재귀함수는 대회 시간이 경과된 경우와 눈덩이가 앞마당의 끝에 도달한 경우에 종료되도록 했다. for문을 사용하여 눈덩이를 굴리는 경우와 눈덩이를 던지는 경우를 나누어 구현했다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

vector<int> snow(101);	// 눈덩이 크기
int N, M;
int answer = 0;	// 가장 큰 눈덩이 크기

void func(int time, int size, int pos) {
	if (time == M or pos >= N) {	// 대회 시간이 경과된 경우 또는 눈덩이가 앞마당의 끝에 도달한 경우
		answer = max(size, answer);
		return;
	}

	// 눈덩이를 굴리는 경우와, 던지는 경우
	for (int i = 1; i <= 2; i++) {
		if (i == 1) {
			func(time + 1, size + snow[pos + i], pos + i);	// 눈덩이를 굴리는 경우
		}
		else
			func(time + 1, (size / 2) + snow[pos + i], pos + i);	// 눈덩이를 던지는 경우
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		cin >> snow[i];
	}
	
	func(0,1,0);
	cout << answer;

	return 0;
}