๐ฃ ๋ฌธ์ ์ดํด
N๊ฐ (20๊ฐ ์ดํ) ์ ์ ์๋ก ์ด๋ฃจ์ด์ง ์์ด์ด ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๊ณ
๊ทธ ์์ด ๋ด์์ ์์ ๊ฐ์๊ฐ ์์์ธ ๋ถ๋ถ์์ด ์ค ํฉ์ด S ์ธ ์์ด์ ๊ฐ์๋ฅผ ๊ตฌํ๋ผ๋ ๋ฌธ์ ์ด๋ค.
๋ฌธ์ ๋ฅผ ํ๋ฉด์ DFS, ๋ฐฑํธ๋ํน์ด ์๊ฐ๋ฌ๊ณ , ์ค์ ๋ค๋ฅธ ๋ธ๋ก๊ฑฐ ๋ถ๋ค๋ ๊ทธ๋ ๊ฒ ํ์ด๋ฅผ ํ๋ ๊ฒฝ์ฐ๋ ์์๋ค.
DFS์ ๋ฐฑํธ๋ํน ๋ฌธ์ ํ์ด๋ฅผ ํ ๋, ๊ทธ ๋ฐฉ์์ผ๋ก๋ ํ์ด๋ณด๊ธฐ๋ก ํ๊ณ ,
์ด๋ฒ์๋ ๋ํ ์์ ํ์(Brute-force Search) ๋ฐฉ์์ ์ฌ์ฉํ๊ธฐ๋ก ํ๋ค. (์ด๋ฆ์ ๊ทธ๋ ๊ณ ์ํผ ์ฌ๊ทํธ์ถํจ..)
๐ญ ํ์ด ๊ณผ์
์์ฑ ์ธ์ด: C++
#include <cstdio>
int num[25] = {0,};
int inpCnt = 0, inpSum = 0, answer = 0;
void count(int pIndex, int pSum){
pSum += num[pIndex];
// ๋๊ฒจ๋ฐ์ ์ธ๋ฑ์ค๊ฐ ์
๋ ฅ๋ฐ์ ์ซ์์ ๊ฐ์๋ฅผ ๋์ ๊ฒฝ์ฐ ์ข
๋ฃ.
if (pIndex >= inpCnt) return;
if (pSum == inpSum) answer++;
count(pIndex + 1, pSum - num[pIndex]); // ์๊ธฐ ์์ ์ ์ ์ธํ ํฉ์ ๋๊ฒจ์ค
count(pIndex + 1, pSum); // ์๊ธฐ ์์ ์ ํฌํจํ ํฉ์ ๋๊ฒจ์ค
}
int main(){
scanf("%d %d", &inpCnt, &inpSum);
for (int i = 0; i < inpCnt; ++i) {
scanf("%d", &num[i]);
}
// ๋งจ ์ฒ์์ ๋ฐฐ์ด์ ์ฒซ๋ฒ์งธ ์์๋ถํฐ ๋ํ๊ธฐ ์์ํ๊ณ , ์์ง ํฉ์ 0์ด๋ค.
count(0, 0);
printf("%d\n", answer);
return 0;
}
๐ ๋ฐฐ์ด ์
์ต์ ์ ๊ฒฝ์ฐ๋ผ ํ๋๋ผ๋ 220 ์ ๋๋ผ์(์ฝ 1,000,000) ๊ฐ๋ฅํ ์ฌ๊ทํธ์ถ ๋ฐฉ๋ฒ์ด์๋ค.
์ดํ์ DFS, ๋ฐฑํธ๋ํน์ ๋ค๋ฃฐ ๋ ๋ค์ ํ์ด๋ณด๋ฉด์ ๋น๊ตํ๋ฉด ์ข์ ๊ณต๋ถ๊ฐ ๋ ๊ฒ ๊ฐ๋ค.