백준 / 백트래킹 / N과 M (8) (boj15657, c11)

문제

---

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

15657번: N과 M (8)

 

입출력

---

 

해설

---

이 문제는 백트래킹의 기본 문제이다.

 

하지만 수열을 1,2와 다르게 이번 백트래킹 문제는 따로 번호를 뽑았는지에 관해서 정보를 저장하고 있을 필요가 없다.

 

중복으로 뽑아도 되기 때문이다.

 

그럼 어떤 식으로 뽑는지 규칙을 살펴보자.

 

9,8,7,1 에서 2개를 뽑아서 나열하는 방법을 한 번 보자.

 

나오는 수열은 오름차순으로 나와야 하기 때문에 뽑기 전에 정렬하는 것이 제일 좋다.

 

그럼 1,7,8,9 라고 생각하고 뽑아보자.

 

일단 1,1 을 먼저 뽑고 맨 앞 1은 놔둔 상태로 7,8,9를 연속해서 뽑아낼 것이다.

 

즉 인덱스로 따져보면

0,0

0,1

0,2

0,3이다.

 

그 다음은 ?

(7,7) , (7,8), (7,9)이다.

인덱스는

1,1

1,2

1,3 이다.

 

어떤 규칙인지는 대충 나온 것 같다. 마지막으로 한 번 더 해보자.

 

(8,8), (8,9) 이다.

인덱스는

2,2

2,3 이다.

 

n*n*~ for문으로 계속 돌리는 것이다.

하지만 for문을 0번부터 계속 돌리는 것이 아니라 전에 idx이상으로만 돌릴 수 있다.

 

그렇기에 백트래킹의 매개변수로는 depth, idx를 갖고 가야 된다.

 

전에 idx를 기억하고 있어야 하며, 깊이를 알고 있어야 종료를 할 수 있기 때문이다.

 

idx==m 이면 종료하면 되고, for문의 시작을 idx로 하면 된다!

 

정답코드

---

#include <stdlib.h>
#include <stdio.h>
/*
 https://www.acmicpc.net/problem/15657
 15657번 N과 M (8)
 0,0
 0,1
 0,2
 0,3
*/

typedef long long ll;

typedef struct node{//해당하는 값을 arr로 갖는다.
    int v;
}node;

typedef struct vector{//인덱스 접근 가능해야 하며, size 존재, back, pop_back,
    node* arr;//값을 저장하는 곳
    ll size;//크기
    ll capacity;//전체 크기
}vector;

void init(vector *q){
    q->arr=(node *)malloc(sizeof(node)*(64));
    q->size=0;
    q->capacity=64;//초기 크기 64개
}

void push_back(vector *q,int v){//v가 추가되기.
    if(q->size+1<=q->capacity){//
        q->arr[q->size].v=v;
    }else{
        ll new_size= q->capacity*2;
        q->arr = (node*)realloc(q->arr,sizeof(node)*new_size);
        q->arr[q->size].v=v;
        q->capacity=new_size;
    }
    q->size++;//크기 증가
}

void pop_back(vector *q){
    if(q->size){//없을 때는 불러내면 안됨.
        q->size--;//값 줄이기
    }else{
        printf("size가 0이므로 더이상 못 뺌\n");
    }
}

node* back(vector *q){
    node* ret = &q->arr[q->size-1];
    return ret;//값 넘겨주기
}
int n,m;
vector *arr;
int cmp(void *a,void *b){
    return (*(node *)a).v-(*(node *)b).v;
}
void backt(int depth,int idx,vector *result){
    if(depth == m){
        for(int i=0;i<m;i++)printf("%d ",result->arr[i].v);
        printf("\n");
        return;
    }
    for(int i=idx;i<n;i++){
        result->arr[depth].v=arr->arr[i].v;
        backt(depth+1,i,result);
        result->arr[depth].v=0;
    }
}
main(){scanf("%d %d",&n,&m);
    arr= (vector*)malloc(sizeof(vector));
    vector *result = (vector *)malloc(sizeof(vector));
    init(arr),init(result);
    for(int i=0,t;i<n;i++)scanf("%d",&t),push_back(arr,t);
    qsort(arr->arr,n,sizeof(node),cmp);
    backt(0,0,result);
}