백준 6603 로또

https://www.acmicpc.net/problem/6603

6603번: 로또

문제에 보면 모든순열같이 숫자를 배치하는 것은 비슷하지만 대신 오름차순으로만 된것을 뽑아야합니다.

그렇게 하려면 탈출조건을 위해  idx 한개의 변수와 s 변수는  1 2 3 4 이렇게 중복없이 무조건 올므차순이 될수 있도록

해주는 변수라고 생각하시면됩니다.

저렇게 써주면 알아서 위치에 들어가게 할수 있고 좀더 정확히 한다면

이렇게 해서 백트래킹 기본 형식으로 하는것 둘다 같은 것이니 편한거 쓰시면됩니다.

이런식으로 재귀를 구현하게되면 순열이긴하지만 조합에 더 가깝다 할수 있는 문제였네요

이유는  N이 몇이 들어올지 모르지만 그중에 6개 의 숫자를 뽑아내야하니까요 무튼 

 1 2 2 3 4 5 6 7 8 이라면

위와 같이 구현한다면

 

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 5 8
1 2 3 4 6 7
1 2 3 4 6 8
1 2 3 4 7 8
1 2 3 5 6 7
1 2 3 5 6 8
1 2 3 5 7 8
1 2 3 6 7 8
1 2 4 5 6 7
1 2 4 5 6 8
1 2 4 5 7 8
1 2 4 6 7 8
1 2 5 6 7 8
1 3 4 5 6 7
1 3 4 5 6 8
1 3 4 5 7 8
1 3 4 6 7 8
1 3 5 6 7 8
1 4 5 6 7 8
2 3 4 5 6 7
2 3 4 5 6 8
2 3 4 5 7 8
2 3 4 6 7 8
2 3 5 6 7 8
2 4 5 6 7 8
3 4 5 6 7 8

 

오름차순으로 중복없이 숫자를 뽑아 낼수 있습니다. 참고 해주세요 .

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int N;
int input[14];
int Lot[6];
int chk[6];
void dfs(int s, int idx) {
    if (idx == 6) {
        for (int y = 0; y < 6; y++) printf("%d ", Lot[y]);
        printf("\n");
        return;
    }
    else {
        for (int i = s; i < N; i++) {
            Lot[idx] = input[i];
            dfs(i + 1, idx + 1);
        }
    }
}
int main(void) {
    while (scanf("%d", &N)&&N!=0) {
        for (int i = 0; i < N; i++) {
            scanf("%d", &input[i]);
        }
        sort(input, input + N);
        dfs(0,0);
        printf("\n");
        memset(input, 0, sizeof(input));
        memset(chk, 0, sizeof(chk));
 
    }
    return 0;
}