[BOJ] 15649. N과 M (1) (C++)

• 코딩 초보

---

15649. N과 M (1) (실버3)

 

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

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

 

출력

 

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

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

 

 

#include <iostream>
#include <vector>
using namespace std; 

int n, m; 
vector <int> v; 
int chk[9] = { 0, }; 

void func(int k) {
	if (k == m) {
		for (int i = 0; i < m; i++) {
			cout << v[i] << " ";
		}
		cout << "\n"; 
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (chk[i] == 1) continue; //이미 방문한 것. continue한다. 
			chk[i] = 1; 
			v.push_back(i); 
			func(k + 1); //재귀호출. 
			v.pop_back();
			chk[i] = 0; 
		}
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m; 

	func(0); 


	return 0; 
}

예전에 파이썬으로 한번 풀었었던 문제이다. 이런 순열과 같은 문제는 재귀 개념을 많이 사용하는 것 같다. 

func()이라는 함수를 만들어서 재귀적으로 호출하도록 하였다. 

전체적인 흐름으로는 func에 오는 매개변수 값이 m과 같아지게 되면 vector에 push된 값들을 모두 출력하도록 하고, pop_back을 순차적으로 진행하여 1,2,3 ... 1,2,4 순으로 출력될 수 있게 해주었다. 

그러니까 1,2,3을 출력하고나서 3을 pop_back(+미방문처리)을 한 후, for문에서 다음 4를 방문처리하여 push해주도록 하는 것이다. 

 

처음에 생각해내기는 어려운데 이런 문제는 익숙해지면 좋을 것 같다.