취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24884번 문제인 장작 넣기이다.
문제는 아래 링크를 확인하자.

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

문제에 주어져있는 조건을 꼼꼼히 잘 읽고 가능한 모든 SKH의 움직임의 경우를 따라 시뮬레이션하여 T시간 뒤에 살아남은 모닥불의 개수가 K개 이상인 경우의 수를 계수하자.

문제에서 주어진 모닥불의 index가 0-based라는 점에 주의하여 구현하자. 또한, 장작을 넣는 행동과 모닥불의 화력간의 관계를 오인하지 않고 문제에서 주어진 대로만 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, W, T, K;
int ans = 0;
void func(vector<int> VEC, int curTime, int idx) {
	if (curTime == T) {
		int cnt = 0;
		for (auto x : VEC) {
			if (x) cnt++;
		}
		if (cnt >= K) ans++;
	}
	else {
		vector<int> diff(N), vec = VEC;
		for (int i = 0; i < N; i++) {
			diff[i] = 3;
			if (i > 0) {
				if (vec[i - 1]) diff[i]--;
			}
			if (i < N - 1) {
				if (vec[i + 1]) diff[i]--;
			}
		}
		for (int i = 0; i < N; i++) {
			vec[i] -= diff[i];
			vec[i] = max(vec[i], 0);
		}
		vec[idx] = VEC[idx];
		func(vec, curTime + 1, idx);

		idx--;
		vec = VEC;
		if (idx > -1) {
			for (int i = 0; i < N; i++) {
				diff[i] = 3;
				if (i > 0) {
					if (vec[i - 1]) diff[i]--;
				}
				if (i < N - 1) {
					if (vec[i + 1]) diff[i]--;
				}
			}
			for (int i = 0; i < N; i++) {
				vec[i] -= diff[i];
				vec[i] = max(vec[i], 0);
			}
			vec[idx] = VEC[idx];
			func(vec, curTime + 1, idx);
		}

		idx += 2;
		vec = VEC;
		if (idx < N) {
			for (int i = 0; i < N; i++) {
				diff[i] = 3;
				if (i > 0) {
					if (vec[i - 1]) diff[i]--;
				}
				if (i < N - 1) {
					if (vec[i + 1]) diff[i]--;
				}
			}
			for (int i = 0; i < N; i++) {
				vec[i] -= diff[i];
				vec[i] = max(vec[i], 0);
			}
			vec[idx] = VEC[idx];
			func(vec, curTime + 1, idx);
		}
	}
}

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

	cin >> N >> W >> T >> K;
	vector<int> vec;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		vec.emplace_back(x);
	}

	vector<int> diff(N);
	for (int i = 0; i < N; i++) {
		diff[i] = 3;
		if (i > 0) {
			if (vec[i - 1]) diff[i]--;
		}
		if (i < N - 1) {
			if (vec[i + 1]) diff[i]--;
		}
	}
	for (int i = 0; i < N; i++) {
		vec[i] -= diff[i];
		vec[i] = max(vec[i], 0);
	}

	func(vec, 1, W);

	cout << ans;
}