N과 m (9)

[Silver III] N과 M (8) - 15657

문제 링크

성능 요약

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

분류

백트래킹

제출 일자

2024년 1월 1일 20:26:48

문제 설명

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

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

입력

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

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

출력

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

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

TIL

• 단순히 isVisted가 아니라 중복도를 고려하는 좀더 일반화된 BackTracking 문제
• 중복도를 체크하는 알고리즘

BackTracing

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

FeedBack

• 중복도를 체크하기 위해 하나의 for문에 i,j두개의 변수를 이용했다. 신선하고 나 스스로 이 방법을 생각한게 뿌듯하다.
• 바로 정답까지 맞아서 뿌듯.

내 접근

input을 받고, 이를 selectionSort.
그리고 중복도를 체크해서 새로운 배열에 담는다.
이때의 배열은 구조체 배열로 {숫자,중복도}를 가진다.
가지치기를 할때 중복도를 빼고, 더한다.

내 코드

#include <stdio.h>
#define SIZE 9

typedef struct{
    int num;
    int repeat;
}Number;

void selectionSort(int arr[],int size);
void getCombination(Number list[],int N,int arr[],int M,int depth);

int main(){

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

    //selectionSort
    selectionSort(input,N);
    

    //countRepeated
    for(size_t i=0,j=0;i<N;i++,j++){
        if(i&&input[i]==input[i-1]) j--;
        list[j].num=input[i];
        list[j].repeat++;
    }
  
  	//getCombination
    int arr[SIZE]={0};
    getCombination(list,N,arr,M,0);


    return 0;
}

//select arr[depth]
void getCombination(Number list[],int N,int arr[],int M,int depth){
    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
        if(list[i].repeat){
            arr[depth]=list[i].num;
            list[i].repeat--;
            getCombination(list,N,arr,M,depth+1);
            //backtracking
            list[i].repeat++;
        }
    }
}

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[j]<arr[minIndex]) minIndex=j;
        int temp=arr[minIndex];
        arr[minIndex]=arr[i];
        arr[i]=temp;
    }
}

Feedback

다른 사람코드 구경한 결과
1티어 : 사전순으로 출력되는 것을 이용하여 마지막으로 출력된 놈의 마지막 항만 다르면 되는 것을 이용하여 풀었다. 가지치기 할때 마지막으로 방문한 놈과 비교해서 같으면 가지치는 방식으로.
2티어 : 내 방식, 각 숫자의 중복도 저장하는 방법
3티어 : 모든 수열을 set에 저장시키는 방법

다른 사람들의 코드를 보니까, 반성하게 된다.
맞혀서 좋아했는데 내 방법은 진짜 정직하게 중복도를 하나하나 세서 시간이 더 오래걸리는 코드임을 알게 되었고 문제 상황을 보고 더 효율적인 코드를 작성해야겠다. 이렇게 naive한 코드말고 문제 상황에 Fit하는 코드를 작성해보자.

문제상황을 그려서 생각해보는 습관부터 잡아야겠다.

1티어 참고코드