[완전 탐색] 백준 문제 풀이 - 15650 N과 M (2)

👩🏻‍💻 문제링크

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

15650번: N과 M (2)

 

 

재귀랑 좀 친해져야 할거 같아서 강의 먼저 봄

✍️ 아이디어 (풀이1 : 순서느낌으로)

1. 문제 이해

• 1부터 N까지 자연수 중 중복없이 M개를 고름 + 오름차순

2. 오름차순이니까 이전자리에 들어간 수가 어떤수인지 재귀 인자로 넘겨주면 그거보다 큰녀석을 탐색하면 됨 

3. 어쩌피 이전 자리 수보다 큰 수만 선택될거니까 따로 수가 전에 나왔는지 check 안해도 됨 (어쩌피 이전자리수가 가장 큰수인데 그거보다 큰수니까 쓰였을리가 없지.)

 

✍️소스코드

• 순열느낌의 코드

#include <iostream>
using namespace std;
int a[10];
int n,m;
void go(int index, int start) 
{//index는 현재 넣을 수의 위치 start는 이전 수의 값
    if (index == m) {
        for (int i=0; i<m; i++) {
            cout << a[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i=start; i<=n; i++) { //이전 수보다 큰녀석중에 골라
        a[index] = i;
        go(index+1, i+1);
    }
}
int main() {
    cin >> n >> m;
    go(0,1);
    return 0;
}

 

✍️ 아이디어 (풀이2 : 선택 느낌으로)

1. 문제 이해

• 1부터 N까지 자연수 중 중복없이 M개를 고름 + 오름차순

2. 수를 1,4를 고르던 4,1을 고르던 둘다 답은 1,4임 (오름차순이라고 순서를 정해줬으니까 => 조합느낌)

3. 특정수를 고르는 경우와 안고르는 경우로 나눔

 

✍️소스코드

• 조합 느낌의 코드

#include <iostream>
using namespace std;

int result[9];
int n,m;

void dfs(int idx, int size)
{
	if(size==m)
	{
		for(int i=0; i<m; i++)
		{
			cout<<result[i]<<' ';
		}
		cout<<'\n';
		return;
	}
	if(idx>n) return;
	result[size]=idx; //숫자 idx를 선택하는 경우
	dfs(idx+1, size+1);
	result[size]=0; //숫자 idx를 선택하지 않는 경우
	dfs(idx+1,size);
}

int main()
{
	cin>>n>>m;
	dfs(1,0);
}

 

 

체감난이도	걸린시간	참고	사용 문법
??	??	강의 참고	재귀, 완전탐색(순열,조합)