Algorithm/problem

백준 15650번: N과 M (2) - 순열의 조합 문제 DFS로 풀기

DingCoDing 2022. 1. 22. 14:03
반응형

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

 

15650번: N과 M (2)

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

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;

int n, r;
int ch[20];
// 1 2 3
// 1 고르거나 안고르거나
// 2 고르거나 안고르거나
// 3 고르거나 안고르거나
// -> 끝고른거 갯수가 r 이면 출력 아니면 그냥 리턴

void DFS(int num, int selected){
	if(num > n) return;
	if(selected==r){
		for(int i=1; i<=n; i++){
			if(ch[i]==1){
				printf("%d ", i);
			}
		}
		printf("\n");
		return;
	}
	else{
		ch[num+1] = 1;
		DFS(num+1, selected+1);
		ch[num+1] = 0;
		DFS(num+1, selected);
	}
}
 

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> r;
	
	DFS(0,0);
}

 

 

 

#include <bits/stdc++.h>
using namespace std;

int n, r;
int ch[20];
// 1 2 3
// 1 고르거나 안고르거나
// 2 고르거나 안고르거나
// 3 고르거나 안고르거나
// -> 끝고른거 갯수가 r 이면 출력 아니면 그냥 리턴

void DFS(int s, int L){
	if(L==r){
		for(int i=0; i<L; i++){
			printf("%d ",ch[i]);
			
		}
		printf("\n");
	}
	else{
		for(int i=s; i<=n; i++){
			ch[L] = i;
			DFS(i+1, L+1);
		}
		
	}
}

int main(){
	//freopen("input.txt.txt","rt",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> r;
	
	DFS(1,0);
}
반응형