์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ๋”ฐ์ง€๊ธฐ ์œ„ํ•ด์„œ ๊ฐ ์ถ”๊ฐ€ ๊ตฌ์Šฌ ๋ฐ˜๋Œ€์ชฝ์— ์˜ฌ๋ผ๊ฐ€๋Š” ๊ฒฝ์šฐ, ์ €์šธ์— ์•ˆ์˜ฌ๋ผ๊ฐ€๋Š” ๊ฒฝ์šฐ, ๊ตฌ์Šฌ๊ณผ ๊ฐ™์€ ์ชฝ์— ์˜ฌ๋ผ๊ฐˆ ๊ฒฝ์šฐ๋ฅผ ๋ชจ๋‘ ๊ณ ๋ คํ•ด์•ผํ•จ

  • ๋ฐฐ๋‚ญ๋ฌธ์ œ๋ฅผ ์‘์šฉํ•˜์—ฌ, ์ถ”๋ฅผ ํ•˜๋‚˜์”ฉ ๋ชจ๋“  ๋ฌด๊ฒŒ์— ๋Œ€ํ•ด ๊ฒ€์‚ฌ๋ฅผ ํ•œ๋‹ค.

    • true์ด๋ฉด ๊ตฌ์Šฌ ๋ฐ˜๋Œ€์ชฝ ์ €์šธ์— ์ถ”๋งŒ์œผ๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ฌด๊ฒŒ๋ผ๋Š” ๋œป.
    • ํ˜„์žฌ ์ถ”๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ฌด๊ฒŒ๋ฉด trueํ‘œ์‹œ
    • ํ˜„์žฌ ์ถ”๋ฅผ ์‚ฌ์šฉํ•˜์ง€์•Š๊ณ  ์ด์ „ ์ถ”๋กœ๋งŒ์œผ๋กœ๋„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ฌด๊ฒŒ๋ฉด, ํ˜„์žฌ์ถ”๋ฅผ ๊ตฌ์Šฌ๊ณผ ๊ฐ™์€ ์ €์šธ์— ๋†“๊ณ  ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ฌด๊ฒŒ๋„ true ํ‘œ์‹œ
  • ์œ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ง„ํ–‰ ํ›„ ๋งˆ์ง€๋ง‰ ์ค„์— ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ๊ฒฝ์šฐ์— true๊ฐ€ ํ‘œ์‹œ๋˜์–ด์žˆ๋‹ค.

์ฝ”๋“œ

#include <iostream>
 
using namespace std;
 
int n, w[30];
bool check[31][15001];
 
int abs(int a) {
	return a < 0 ? -a : a;
}
 
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> w[i];
	for (int i = 0; i <= 30; i++)
		check[i][0] = true;
 
	for (int j = 1; j <= n; j++) {
		for (int i = 1; i <= 15000; i++) {
			if (w[j - 1] <= i && check[j - 1][i - w[j - 1]]) {
				check[j][i] = true;
			}
			else if (check[j - 1][i]) {
				check[j][i] = true;
				check[j][abs(i - w[j - 1])] = true;
			}
		}
	}
 
	int c, t;
	cin >> c;
	for (int i = 0; i < c; i++) {
		cin >> t;
		if (t > 15000)
			cout << "N ";
		else if (check[n][t])
			cout << "Y ";
		else
			cout << "N ";
	}
 
}