https://www.acmicpc.net/problem/6603
6603번: 로또
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로
www.acmicpc.net
🔔 문제 :
{1, 2, ..., 49} 사이의 수에서 로또의 수를 구할 수 있습니다.
6<k<13 범위의 정수 k를 정하여, k개 만큼 숫자를 정해놓고 로또의 숫자인 6개를 만들 예정입니다.
k개의 수에서 로또의 숫자 6개가 되는 경우의 수들을 찾는 문제입니다.
🔔 Kick Point :
k개중 6개를 뽑는 조합의 수를 찾으면 되는 문제입니다.
이때 DFS(깊이우선탐색)을 통하여 찾았고, 순서와 상관없이 수를 뽑는 조건이기에 DFS에 매개변수 N을 두어 전 자리수의 수보다 이후의 자리수의 수가 더 크게 만들었습니다.
조합에 관한 자세한 설명이 필요하시다면 이 포스트를 참고하시면 좋겠습니다.
2022.03.03 - [백준] - [C++][백준] - N과 M (2) (15650번)
[C++][백준] - N과 M (2) (15650번)
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
meta-jun.tistory.com
🔔 Code :
변수
Arr[MAX] : k개의 숫자를 담아두는 공간
G_Nrr[MAX] : DFS를 통하여 만들어진 경우의 수를 담아두는 공간
G_Visitied[MAX]: 수가 사용 됐는지를 파악하기 위한 배열
G_N : 위 문제에서의 k
함수
Input: Arr[i]에 수를 담는 함수
Reset: 여러번의 함수 실행을 위하여 리셋하는 함수
DFS: 재귀적인 방법으로 백트래킹을 통하여 경우의 수를 구하는 함수
#include <iostream>
#define MAX 13
using namespace std;
int Arr[MAX];
int G_Nrr[MAX];
bool G_Visitied[MAX] = {false,};
int G_N;
void Input(int N) {
for (int i = 0; i < N; i++) {
cin >> Arr[i];
}
}
void Reset() {
for (int i = 0; i < MAX; i++) {
G_Visitied[i] = false;
G_Nrr[i] = 0;
}
}
void DFS(int N = 0, int cnt = 0) {
if (cnt == 6) {
for (int i = 0; i < 6; i++) {
int tmp = G_Nrr[i];
cout << Arr[tmp] << ' ';
}
cout << '\n';
}
for (int i = N; i < G_N; i++) {
if (!G_Visitied[i]) {
G_Nrr[cnt] = i;
G_Visitied[i] = true;
DFS(i + 1, cnt + 1);
G_Visitied[i] = false;
}
}
}
int main() {
while (cin >> G_N) {
Input(G_N);
DFS();
Reset();
cout << '\n';
if (G_N == 0) break;
}
}
