백준 20167 꿈틀꿈틀 호석 애벌레(기능성) C풀이 - DFS

내 친구 호석이가 애벌레가 되어버린 문제이다.

호석이는 한 번 시작하면 특정 조건을 만족하기 전까지는 연속해서 먹이를 먹는다.

탙피 에너지를 최대한으로 축적하고 싶은데, 얼마나 축적할 수 있는지를 계산해보자.

 

문제의 조건은 다음과 같다.

1. 탈피 에너지를 최대한으로 쌓을 것

2. 먹이를 하나 먹으면 조건을 만족할 때까지 계속 먹을 것

 

문제의 접근 방식은 다음과 같다.

1. 먹이를 먹을 수도 안먹을 수도 있기 때문에 단순 루프로 접근하려면 케이스를 여러개 고민해줘야한다.

2. 애벌레의 다음 행동은 지난 행동에게 영향을 받는다. (직전 먹이를 먹었다 -> 조건 만족하면 멈추고 만족못하면 계속 먹어야함,   직전 먹이를 먹지 않았다 -> 이번 먹이를 먹을수도 안먹을수도 있다.)

3. 당장 최대한으로 만들 수 있는 먹이를 선택할 경우(GREEDY) 뒤의 더 큰 에너지 축적기회를 날릴 수 있다. -> 모든 경우 탐색

 

문제의 해결 방식은 다음과 같다.

1. 모든 경우를 탐색한다.

2. 저번 먹이를 먹고 조건을 만족할 경우(SUM >=K) 이번 먹이를 먹을수도 안먹을수도 있다.

3. 저번 먹이를 먹고 조건이 만족되지 않을 경우 이번 먹이는 반드시 먹는다.

4. 저번 먹이를 먹지 않았다면 이번 먹이는 먹을수도 안먹을수도 있다.

 

이 4가지의 경우를 DFS 로 구현하여 모든 방법을 탐색했다.

 

전체 코드

#include <stdio.h>
int N, K;
int Feed[21];
int Max;

void solve(int num, int p_sum , int energy, int prev) {
	if (num == N) {
    	//먹이 끝에 도달했을 경우
        //소화 다 안됐어도 탈피 에너지에 축적됨 -> 최댓값 갱신
		if (energy + (p_sum>=K?p_sum-K:0)> Max) Max = energy + (p_sum >= K ? p_sum - K : 0);
		return ;
	}
    //저번먹이까지 진행 후 조건에 만족할 경우
	if (p_sum >= K) {
    	//이번 먹이를 먹기
		solve(num + 1, Feed[num], energy + p_sum - K, 1);
        //이번 먹이 안먹기
		solve(num + 1, 0, energy + p_sum - K, 0);
	}
    //저번먹이까지 진행했으나 조건에 만족하지 않을 경우
	else {
    	//저번먹이를 먹었다면
		if (prev) {
        //반드시 먹어야함
			solve(num + 1, p_sum + Feed[num], energy, 1);
		}
        //먹지 않았었다면
		else {
        	//안먹어도 되고
			solve(num + 1, p_sum, energy, 0);
            //먹어도됨
			solve(num + 1, p_sum + Feed[num], energy, 1);
		}
	}
	return;
}

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d", &Feed[i]);
	}
	solve(0, 0, 0, 0);
	printf("%d\n", Max);
	return 0;
}