N과 m (12)

[Silver II] N과 M (12) - 15666

문제 링크

성능 요약

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

분류

• 백트래킹

제출 일자

• 2024년 1월 6일 23:59:18

문제 설명

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

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

입력

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

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

출력

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

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

TIL

• 방문한 노드보다 작으면 안되는 것을 이전까지는 isVisted배열을 추가로 할당하여 오르차순을 성립시켰으나, start를 매개변수로 재귀함수에 집어넣으면 더 간단히 동일한 로직을 구현할 수 있다.

BackTracing

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

내 접근

가지치는 조건이 2개이다.

1. 같은 level의 이전 노드와 같은 값을 가지면 안됨(중복) -> previousNodeValue와 비교하여 제거

2. 방문한 노드보다 작으면 안됨(오름차순)-> 처음에는 isVisted배열 이용, 그러나 start변수를 이용하여 코드 개선

   

내 코드

#include <stdio.h>

#define SIZE 9
void selectionSort(int arr[],int size);
void getPermutation(int list[],int start,int N,int result[],int M,int depth,int* previousNodeValue);
int main(){

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

    //getPermutation
    int result[SIZE]={0};
    int previousNodeValue=-1;
    getPermutation(list,0,N,result,M,0,&previousNodeValue);

}


//select result[depth] by using element of list
void getPermutation(int list[],int start,int N,int result[],int M,int depth,int* previousNodeValue){
    if(depth==M){
        for(size_t i=0;i<M;i++)
            printf("%d ",result[i]);
        printf("\n");
        return;
    }

    //spreading 
    for(size_t i=start;i<N;i++){
        //pruning : except equal to previousNodeValue
        if(list[i]!=*previousNodeValue){
            result[depth]=list[i];
            *previousNodeValue=-1;
            //pruning : except lower value
            getPermutation(list,i,N,result,M,depth+1,previousNodeValue);
            //backtracking
            *previousNodeValue=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

저번까지는 오름차순을 유지하기 위해서 추가적인 배열을 이용했었는데, 이번에도 그렇게 하고 다른 사람의 코드를 보고 이해하려 노력해서 수정했다.

답은 간단한데, 현재 노드 이상의 값을 가지기 위해선 start에 i를 집어 넣기만 하면 되기때문.

직접 생각하려고 해봤는데, 안돼서 다른 사람꺼 답을 보니까 다시 쉬워보이긴 한다. ㅋㅋㅋ

그래도 성장한 것에 의미를 두고, 이렇게 M과 N시리즈를 다 풀어보았는데 덕분에 재귀적 사고와 백트래킹에 대해 익숙해지게 되었다.