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

<문제>

---

<Code>

//21735] 눈덩이 굴리기 
#include <iostream>
#include <algorithm>
using namespace std;

int n, m, res;
int map[101];

void DFS(int l, int val, int mv){ //level, value, move(m만큼) 
	if(l==m){ //시간되면 눈덩이 크기 비교해서 최댓값 저장 
		res=max(res, val);
		return;
	}else{
	 //굴리고(+1) 그대로 더하거나, 던지고(+2) 절반 깎은다음 더하거나 
		DFS(l+1, val+map[mv+1], mv+1);
		DFS(l+1, val/2+map[mv+2], mv+2);
	}		
}

int main() {
	freopen("input.txt","rt", stdin);
	scanf("%d %d", &n, &m); 
	for(int i=1; i<=n; i++){
		scanf("%d", &map[i]);
	}
	
	DFS(0, 1, 0); //time, value, move(m만큼) 
	printf("%d", res);
	return 0;
}

---

<Comment>

다른 블로그를 보니 DP로도 푼 사람이 있다고 하던데 DP고 뭐고 무조건 DFS라는 생각밖에 안들었다.

간단하게 상태탐색트리 그림 그렸고,

level, value(눈덩이 크기), move(굴리는지/던지는지) 이렇게 3가지를 인자로 넘기는 이름 그대로의 DFS함수로 풀었다.

 

---

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

21735번: 눈덩이 굴리기