[백준] 15652번 : N과 M (4) [C/C++]

#문제

15652번: N과 M (4)

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

15652번: N과 M (4)

 

---

#접근방법

이 문제는 어제 푼 문제 15652번 : N과 M (2)와 매우 유사한 문제이다.

 

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열을 비내림차순이어야 한다. 

위 조건을 만족하는 수열은 같은 수를 허용하는 오름차 순의 길이가 M인 수열이다.

 

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

 

https://rujang.tistory.com/12

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

어제 푼 문제코드에서 한 줄만 바꾸면 풀 수 있는 문제이다.

반응형

---

#풀이

#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,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, len+1) 재귀함수를 호출한다.

 

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

 

어제 푼 문제와 다른코드는 seq(i+1,len+1)에서 seq(i,len+1)로 바뀌었다는 점이다.

 

i+1을 넣은 경우는 중복을 허용하지 않기 위해 현재까지 만들어진 숫자보다 1더 큰 숫자를 호출해주었다.

 

i를 넣으면 중복을 허용하는 오름차순 수열이 완성된다.

 

---

#성능

---

#정리

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

 

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

 

비슷한 유형의 문제를 풀었을 때, 이용하면 빠르게 풀 수 있는 것,

 

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