[백준] 15650번 : N과 M (2) [C/C++]

#문제

15650번: N과 M (2)

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

15650번: N과 M (2)

 

---

#접근방법

자연수 N과 M이 주어졌을 때,

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

위 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제이다.

 

재귀함수로 백트래킹기법을 사용하여 모든 조합을 구하면 된다.

반응형

---

#풀이

#include <stdio.h>

int n,m;

int arr[10];

void seq(int x,int len){
    if(len==m){
        for(int i=0;i<m;i++)
            printf("%d ",arr[i]);
        printf("\n");
        return;
    }

    for(int i=x;i<=n;i++){
        arr[len] = i;
        seq(i+1,len+1);
    }

    return;
}

int main(){
    scanf("%d %d",&n,&m);

    seq(1,0);

    return 0;
}

 

arr이라는 배열을 하나 만들고 그 안에 중복되지 않는 수열을 넣어준다.

 

처음 seq함수를 호출 할 때, seq(1,0)으로 호출을 해주었다.

 

seq(int x, int len)에서 len은 현재 만들어진 수열의 길이이고, x는 현재 만들어진 수열의 맨 뒤에 붙을 x부터 n까지 숫자이다.

 

반복문으로 arr배열에 중복되지 않는 수열을 넣어주고 seq(i+1, len+1) 재귀함수를 호출한다.

 

이 때, len==m이면 길이가 m인 수열을 만들었다는 뜻이므로 arr배열에 저장해두었던 수열을 출력해주고 return;으로 함수를 종료시키면 풀 수 있는 문제다.

 

---

#성능

---

#정리

모든 조합을 구하는 문제는 백트래킹 기법을 사용해야 한다는 것,

 

백트래킹 기법을 사용하기 위해 자기자신을 호출하는 재귀함수를 쓴다는 것,

 

중복되지 않는 수열을 배열에 저장하여 만들어진 수열의 길이가 m이면 출력하고 종료를 시키는 종료조건문을 넣는다는 것을 알면 풀 수 있는 문제였다.