์๊ณ ๋ฆฌ์ฆ
-
๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ๋ฐ์ง๊ธฐ ์ํด์ ๊ฐ ์ถ๊ฐ ๊ตฌ์ฌ ๋ฐ๋์ชฝ์ ์ฌ๋ผ๊ฐ๋ ๊ฒฝ์ฐ, ์ ์ธ์ ์์ฌ๋ผ๊ฐ๋ ๊ฒฝ์ฐ, ๊ตฌ์ฌ๊ณผ ๊ฐ์ ์ชฝ์ ์ฌ๋ผ๊ฐ ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ ๊ณ ๋ คํด์ผํจ
-
๋ฐฐ๋ญ๋ฌธ์ ๋ฅผ ์์ฉํ์ฌ, ์ถ๋ฅผ ํ๋์ฉ ๋ชจ๋ ๋ฌด๊ฒ์ ๋ํด ๊ฒ์ฌ๋ฅผ ํ๋ค.
- 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 ";
}
}