개인공부/알고리즘

BOJ 21735 [눈덩이 굴리기]

Dev_Camp 2023. 9. 18. 23:18

문제

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

 

21735번: 눈덩이 굴리기

눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은

www.acmicpc.net

 

 

 

풀이

#include <iostream>
using namespace std;

int snow[105];
int N, M;

int bf(int pos, int count, int size){
	if(pos >= N) return size;
	if(count == M) return size;
	int result = 0;
	result = max(bf(pos+1, count+1, size+snow[pos+1]), bf(pos+2, count+1, size/2+snow[pos+2]));
	return result;
}

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

 

풀이 방식은 재귀를 통한 완전탐색을 이용하여 풀었다. 이때 눈이 앞마당을 벗어나거나 시간이 다 되었을 경우를 종료조건으로 설정하였다.