[boj : 20167]꿈틀꿈틀 호석 애벌래-기능성

www.acmicpc.net/problem/20167

20167번: 꿈틀꿈틀 호석 애벌레 - 기능성

문제 : 애벌래는 연속적으로 먹이를 먹을 수 있음. 먹은 먹이들의 합이 k 이상일때 k를 초과한 부분을 축적함. 그리고 다시 0부터 시작. 이때 축적된 양이 최대값이 되게끔 구해라.

 

해설 : n의 범위가 20밖에 안되는걸 보면 모든 경우의 수를 해도 2^20 이니 충분하죠.

그래서 재귀로 싹다 돌렸습니다.

 

#include<bits/stdc++.h>

using namespace std;

int n, k,ans=0;
int arr[20],v[20];

void dfs(int depth, int sum, int prev);

int main()
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	dfs(0,0,0);
	cout << ans;
	return 0;
}
void dfs(int depth, int sum, int prev)
{
	if (depth == n) {
		ans = max(ans, sum);
		return;
	}

	v[depth] = 1;
	prev += arr[depth];
	if (prev >= k) dfs(depth + 1, sum + (prev - k), 0);
	else dfs(depth + 1, sum, prev);
	

	v[depth] = 0;
	dfs(depth + 1,sum,0);
}