12969 ABC

์•Œ๊ณ ๋ฆฌ์ฆ˜(dp)

1. ํ˜„์žฌ ๊นŠ์ด d, ์ด์ „์— ๋‚˜์™”๋˜ a์˜ ๊ฐœ์ˆ˜, ์ด์ „์— ๋‚˜์™”๋˜ b์˜ ๊ฐœ์ˆ˜, ์ด์ œ๊นŒ์ง€์˜ k ์ˆ˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ dp๋ฅผ ๋งŒ๋“ค์–ด์•ผํ•จ. k๋„ ๊ฒฐ๊ณผ์— ์˜ํ–ฅ์„ ์ฃผ๊ธฐ ๋•Œ๋ฌธ.
2. ์ฆ‰, dp[d][a][b][k] ๋ฅผ ์„ ์–ธํ•˜๊ณ , ์ด ์ƒํƒœ๊ฐ€ ๊ฒ€์‚ฌ๋˜๋ฉด true๋กœ ์ง€์ •ํ•˜์—ฌ ๋‹ค์‹œ ๊ฒ€์‚ฌํ•˜์ง€์•Š์Œ.
3. ์ •๋‹ต์„ ์ฐพ์•˜์„ ๋•Œ๋Š” ์ „์—ญ๋ณ€์ˆ˜ got์— true๊ฐ’์„ ์ง€์ •ํ•˜์—ฌ ๋ฐ”๋กœ ๋‹ค๋ฅธ ๋ชจ๋“ ๊ฑธ ์ข…๋ฃŒ์‹œํ‚ค๊ณ  ์ถœ๋ ฅ

์ฝ”๋“œ

#include <iostream>
#include <cstring>
using namespace std;
 
int N, K, num[30], ans[30];
bool save[31][31][31][450], got;
 
void DP(int d, int a, int b, int n);
 
int main() {
	cin >> N >> K;
	memset(num, -1, sizeof(num));
	memset(ans, -1, sizeof(ans));
 
	DP(0, 0, 0, 0);
	if (!got)
		cout << -1 << endl;
	else {
		for (int i = 0; i < N; i++) {
			if (ans[i] == 0)
				cout << 'A';
			else if (ans[i] == 1)
				cout << 'B';
			else if (ans[i] == 2)
				cout << 'C';
		}
	}
}
 
void DP(int d, int a, int b, int n) {
	if (d == N) {
		if (n == K) {
			got = true;
			memcpy(ans, num, sizeof(num));
		}
		return;
	}
	if (save[d][a][b][n])
		return;
	save[d][a][b][n] = true;
 
	if (got)
		return;
 
	num[d] = 0;
	DP(d + 1, a + 1, b, n);
	if (!got) {
		num[d] = 1;
		DP(d + 1, a, b + 1, n + a);
	}
	if (!got) {
		num[d] = 2;
		DP(d + 1, a, b, n + a + b);
	}
	num[d] = -1;
}