[BaekJoon/백준] 15649번

순열과 조합 문제.

 

첨에 조합 문제인 줄 알고 아래처럼 코딩했다

#include <stdio.h>
#include <stdlib.h>
// 조합 문제. 15649번
int *check;
int *b;
int total; //전체에서



void Printt() {
    for(int i = 0; i < total; i++) {
        if(check[i])
            printf("%d ", b[i]);
    }
    putchar('\n');
}
 // size = 배열 크기, n = 이터레이터, max = 뽑을 갯수, count = 뽑은 갯수
void su(int *x, int size, int n, int max, int count) {
    
    if(max == count) {
        Printt();
        return;
    }
    else {
        
        for(int i = n; i < size; i++) {
            if(!check[i]) {
                check[i] = 1;
                su(x, size, i+1, max, count + 1);
                check[i] = 0;
            }
        }
        
    }
    
}

int main() {
     
    int n; // 몇개뽑을지
    
    scanf("%d %d", &total, &n);
    
    b = calloc(total, sizeof(int));
    check = calloc(total, sizeof(int));
    
    for(int i = 0; i < total; i++) {
        b[i] = i + 1;
    }
    
    su(b, total, 0, n, 0);
    
    free(b);
    free(check);
    
}

 

당연히 틀렸다. 이 코드는 조합이므로 (1, 2)랑 (2, 1)은 같은 경우로 생각하여 뽑지 않기 떄문. (코드도 깔끔하지 않으므로, 참고하진 말 것..! 바로 다음 문제에 조합 알고리즘이 나와서 이 코드를 다듬어서 포스팅했다.)

 

그래서 순열로 다시 코딩했다.

#include <stdio.h>
#include <stdlib.h>
// 순열 문제. 15649번

int *b; // 메인 배열의 포인터
int *check; // 뽑았는지 표시할 배열의 포인터
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--; // 출력한 뒤 하나 감소. check[i] = 0 밑에 해줘도 상관없음
}
 // count = 뽑은 갯수
void su(int *x, int count) {
    
    if(nx == count) {
        Printt();
        return;
    }
    else {
        for(int i = 0; i < total; i++) {
            if(!check[i]) {
                check[i] = 1;
                key[p++] = i + 1; // 뽑은값(i는 1부터이므로 +1) 배열에 추가.
                su(x, count + 1);
                check[i] = 0;
            }
        }
        p--;
    }
}

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

조금 더 긴듯! 뽑은 값을 순서대로 저장해줄 배열 역할을 해줄(배열 주소를 가리키는) 포인터 key의 동적할당이 추가되었다.

 

 

---

2021.03.06

 

// 백트래킹

#include <stdio.h>

int N;
int C;

int arr[8];
int arr_b[8];

int key[8]; // 뽑은거

void combine(int count) {
    
    if(count == C) {
        for(int i = 0; i < count; i++) {
            printf("%d ", key[i]);
        }
        putchar('\n');
        return;
    }
    
    for(int i = 0; i < N; i++) {
        
        if(arr_b[i])
            continue;
        
        key[count] = arr[i];

        arr_b[i] = 1;
        combine(count + 1);
        arr_b[i] = 0;
    }
    
}

int main() {
    
    scanf("%d %d", &N, &C);
    
    for(int i = 0; i < N; i++) {
        arr[i] = i + 1;
    }
    
    combine(0);
    
}


// 블랙잭같은경우
// 재귀를 이용한 백트래킹
// 반복문을 이용한 브루트포스
// 두 경우에 대한 모든 구현이 가능했지만, 이 문제의 경우는 N 중 포문에 구현이 처음부터 정해지지 않았기에 두번째 방법으로는 구현이 거의 불가능하다. (가능은 한데, 문제의 최대 뽑는 경우가 8이므로, 처음부터 아예 8중 중첩으로 구현해야 할 것이다)