[BaekJoon/백준] 15652번

연속 4번째 비슷한 유형의 '순열과 조합' 문제

 

이번 문제는 조합문제인데, 같은 수를 여러 번 뽑아도 되는 문제다.

뽑은 결과의 중복은 없어야 하지만, 같은 수를 여러번 뽑아도 된다는 것.

 

바로 이전 문제인 15651번에 변수 하나를 추가하여 문제를 풀 수 있었다.

#include <stdio.h>
#include <stdlib.h>
// 15652번. 이 문제는 조합 알고리즘 기반이고, 같은 수를 여러번 골라도 된다는 사항이 있다.
// 15651번에서 su 함수에 이터레이터 역할을 해줄 n만 추가해줬다. (뒤로는 안가며, 나 자신부터 다시 뽑을 수 있도록 돌리게끔 해줌)

int *b; // 메인 배열의 포인터
int total; //전체에서
int nx; // 몇개뽑을지
int *key; // 뽑은 값 순서대로 저장할 배열 역할해줄(배열 주소를 가질) 포인터.
int p = 0; // key iterator


void Printt() {
    for(int i = 0; i < nx; i++) {
        printf("%d ", key[i]);
    }
    putchar('\n');
    p--; // 출력한 뒤 하나 감소.
}
 // n = 이터레이터, count = 뽑은 갯수
void su(int *x, int n, int count) {
    
    if(nx == count) {
        Printt();
        return;
    }
    else {
        for(int i = n; i < total; i++) {
                key[p++] = i + 1; // 뽑은값(i는 1부터이므로 +1) 배열에 추가.
                su(x, i , count + 1);
        }
        p--;
    }
}

int main() {
         
    scanf("%d %d", &total, &nx);
    
    b = calloc(total, sizeof(int));
    key = calloc(nx, sizeof(int));
    
    for(int i = 0; i < total; i++) {
        b[i] = i + 1; // 1부터 시작이므로.
    }
    
    su(b, 0, 0);
    
    free(b);
    free(key);
    
}