N과 M (1) 15649

N과 M (15649)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 15649 N 과 M 1

int N, M;

void seq(vector<int> &arr){
	
	// 기저 사례 : 길이가 M 에 도달하면 종료
	if(arr.size() == M) {
		for(int a : arr) cout << a << " ";
		cout << "\n";
		return;
	}
	
	for(int i = 1 ; i <= N; i++){
		if(find(arr.begin(), arr.end(), i) != arr.end()) continue;
		arr.push_back(i);
		seq(arr);
		arr.pop_back();
	}
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N >> M;
	
	vector<int> arr;
	
	seq(arr);
}

풀이코드 (메모이제이션)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 15649 N 과 M 1

int N, M;
bool used[10]; // 사용한 것을 저장하는 배열
int arr[10]; // 지금 구성된 수열을 저장하는 배열
// 강의 버전
void seq(int index){
	// 기저 사례 : 길이가 M 에 도달하면 종료
	if(index == M) {
		for(int i = 0; i < M; i++){
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}
	
	for(int i = 1 ; i <= N; i++){
		if(used[i]) continue;
		used[i] = true;
		arr[index] = i;
		
		seq(index + 1);
		
		used[i] = false;
	}
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N >> M;
	
	fill_n(used, 10, false);
	
	seq(0);
}

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

이 문제는 순서와 관련되어 있다. 순서가 매우 중요하다.

첫째 자리에 올 수 있는 것은 1 ~ N 중 하나이다. 

두번째 자리는 1 ~ N 중 하나인데 1번 위치에 올 수 있는 것을 제외한 것이다.

세번째 자리는 1 ~ N 중 하나인데 1, 2 번 위치에 올 수 있는 것을 제외한 것이다.

재귀는 어떤 위치에서든 같은 방법으로 수를 골라야 한다. 말로 표현하자면.

1 ~ N 수 중에서 앞에서 사용하지 않은 수를 고른다!

첫번째 자리에서 두번째 자리로 넘어갈 때 바뀌는 것은

1. 위치

2. 사용 가능한 수 (사용한 수)

이것이 함수의 인자로 보내주면 되겠다.

하나가 넘어갈 때 무엇이 바뀌는지를 잘 파악하자.

재귀란 어떤 위치에 올 수 있는 수를 결정해주는 것

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점