1-A-A 첫번째 문제 백준 15650번 N과 M(2)
15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력..
dongwook-chang.tistory.com
| 결과 수열에 중복이 있는 경우 | 결과 수열에 중복이 없는 경우 | |||
| 순열 P(N,M) | 조합 C(N,M) | 중복조합 H(N,M) | 비내림차순 중복순열 Pie(N,M) s.t non-dcr |
|
| 1부터 N까지의 수 | 입력 수열이 주어지지 않기 때문에 인덱스를 1부터 증가시켜 수열의 항을 대체한다. | |||
| 15649 N과 M(1) | 15650 N과 M(2) | 15651 N과 M(3) | 15652 N과 M(4) | |
| 14913097 void BF(int d) { if (d == M) { //s 출력 return; } for (i=1;i<=N;++i) { if (v[i]) continue; v[i] = 1; s[d] = i; BF(d + 1); v[i] = 0; } } |
14885200 void BF(int i, int d) { if (d == M) { //s 출력 return; } for (;i<=N;++i) { s[d] = i; BF(i + 1, d + 1); } } |
14913228 void BF(int d) { if (d == M) { //s 출력 return; } for (i=1;i<=N;++i) { s[d] = i; BF(d + 1); } } |
14915378 void BF(int i, int d) { if (d == M) { //s 출력 return; } for (;i<=N;++i) { s[d] = i; BF(i, d + 1); } } |
|
| BF(0); | BF(1, 0); | BF(0); | BF(1, 0); | |
| 임의의 N개의 수 (중복 없음) |
인덱스는 0부터 증가시키고 결과 수열에 인덱스 대신 입력 수열의 항을 할당한다. | |||
| 15654 N과 M(5) | 15655 N과 M(6) | 15656 N과 M(7) | 15657 N과 M(8) | |
| 14913449 void BF(int d) { if (d == M) { //s 출력 return; } for (i=0;i<N;++i) { if (v[i]) continue; v[i] = 1; s[d] = sq[i]; BF(d + 1); v[i] = 0; } } |
14913645 void BF(int i, int d) { if (d == M) { //s 출력 return; } for (;i<N;++i) { s[d] = sq[i]; BF(i + 1, d + 1); } } |
14914638 void BF(int d) { if (d == M) { //s 출력 return; } for (i=0;i<N;++i) { s[d] = sq[i]; BF(d + 1); } } |
14915391 void BF(int i, int d) { if (d == M) { //s 출력 return; } for (;i<N;++i) { s[d] = sq[i]; BF(i, d + 1); } } |
|
| BF(0); | BF(0, 0); | BF(0); | BF(0, 0); | |
| 임의의 N개의 수 (중복) |
결과 수열에 중복이 없는 경우, 입력 수열에서의 각 수의 빈도수(cnt[i]) 만큼 사용 가능(v[i]의 기능 포함) | |||
| 15663 N과 M(9) | 15664 N과 M(10) | 15665 N과 M(11) | vN과 M(12) | |
| 14915144 void BF(int d) { if (d == M) { //s 출력 return; } for (i=0;i<sqn;++i) { if (cnt[sq[i]] == 0) continue; --cnt[sq[i]]; s[d] = sq[i]; BF(d + 1); ++cnt[sq[i]]; } } |
15664 void BF(int i, int d) { if (d == M) { //s 출력 return; } for (;i<sqn;++i) { if (cnt[sq[i]] == 0) continue; --cnt[sq[i]]; s[d] = sq[i]; BF(i, d + 1); ++cnt[sq[i]]; } } |
14915661 void BF(int d) { if (d == M) { //s 출력 return; } for (i=0;i<sqn;++i) { s[d] = sq[i]; BF(i, d + 1); } } |
14915793 void BF(int i, int d) { if (d == M) { //s 출력 return; } for (;i<sqn;++i) { s[d] = sq[i]; BF(i, d + 1); } } |
|
| BF(0); |
BF(0, 0); 재귀호출의 인자로 i+1을 넘겨주면 자손에서 같은 숫자가 반복될 수 없으므로 i를 넘겨준다. |
BF(0); | BF(0, 0); | |
|
int i // 입력받은 수열 sq의 인덱스 int v[MAX_N]; // 선택 여부; 인덱스 i가 선택되었는지의 여부를 저장 |
||||