N과 m (10)

[Silver II] N과 M (10) - 15664

문제 링크

성능 요약

메모리: 1116 KB, 시간: 0 ms

분류

백트래킹

제출 일자

2024년 1월 3일 14:57:33

문제 설명

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A₁ ≤ A₂ ≤ … ≤ A_K-1 ≤ A_K를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

TIL

• 이전에 방문한 노드를 이용. 이때 올라오면서 갱신되어야 하므로 재귀함수 호출 이후에 써주기

BackTracing

1. 확장
2. 가지치기
3. 끝까지 간뒤에 다시 올라오기 (이때 원상태로 복원시키면서)

내 접근

백트래킹 문제는 가지치는 부분이 핵심이므로, 이 부분만 살펴보자.
다음 조건이 만족되면 가지를 쳤다.

1. 그 노드보다 큰 값이 방문되었는가? (올림차순)
2. 직전 노드의 값과 같은 값인가? (중복제거)

내 코드

#include <stdio.h>
#include <stdbool.h>
#define SIZE 9
void selectionSort(int arr[],int size);
void getCombination(int list[],int isVisted[],int N,int arr[],int M,int depth,int* previous_node);
int main(){

    //input
    int N,M;
    scanf("%d %d",&N,&M);
    int list[SIZE]={0};
    for(size_t i=0;i<N;i++){
        scanf("%d",&list[i]);
    }
    
    selectionSort(list,N);

    int previous_node=-1;
    int arr[SIZE]={0};
    int isVisted[SIZE]={0};
    getCombination(list,isVisted,N,arr,M,0,&previous_node);
    

    return 0;
}

//select arr[depth]
void getCombination(int list[],int isVisted[],int N,int arr[],int M,int depth,int* previous_node){
    if(depth==M){
        for(size_t i=0;i<M;i++)
            printf("%d ",arr[i]);
        printf("\n");
        return;
    }

    for(size_t i=0;i<N;i++){
        //pruning
        bool flag=true;
        for(size_t j=i;j<N;j++){
            if(isVisted[j]) flag=false;
        }
        if(*previous_node==list[i]) flag=false;
            
        if(flag){
            isVisted[i]=true;
            
            arr[depth]=list[i];
            getCombination(list,isVisted,N,arr,M,depth+1,previous_node);
            //backTracking
            isVisted[i]=false;
            *previous_node=list[i];
        }
    }

}




void selectionSort(int arr[],int size){
    for(size_t i=0;i<size-1;i++){
        int minIndex=i;
        for(size_t j=i+1;j<size;j++)
            if(arr[minIndex]>arr[j]) minIndex=j;
        int temp=arr[minIndex];
        arr[minIndex]=arr[i];
        arr[i]=temp;
    }
}

시간복잡도는
SelectionSort에서 O(N^2)
getCombination에서 O(N^M) 따라서 총 시간복잡도는 O(N^M+N^2)

Feedback

• N과 M(9)처럼 중복도를 일일이 다 세지 않고 직전 노드의 값만 비교하면 되는 것을 이용해 코드를 작성하였다. 다른 사람 코드 보고 이렇게 응용하는게 중요하다.

그리고 오림차순으로 정렬되었음을 활용해서 굳이 해당 노드 값보다 큰 값의 방문여부를 for문 하나하나 돌지 않고도 해결할 수 있던데, 지금은 이해하기 어렵다. 다음 문제 풀때 다시 봐야겠다. ```