N과 M (2) 15650

N과 M (2) (15650)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 15650 N 과 M (2)

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;
		
		arr[index] = i;
		// 순서(크기)를 강제한다. 오름차순이 아니라면 생략하기
		if(arr[index] < arr[index - 1]) continue;
		used[i] = true;
		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);
}

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 15650 N 과 M (2)

int N, M;
bool used[10]; // 사용한 것을 저장하는 배열
int arr[10]; // 지금 구성된 수열을 저장하는 배열
void go(int index, int selected){
	// 기저 사례: 선택한 수 가 M 과 같으면 출력
	if(selected == M){
		for(int i = 0; i < M; i++){
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}
	
	// 범위 초과 시 끝
	if( index > N) return;
	
	// index 라는 값을 selected 번째로 선택하였을 때
	arr[selected] = index;
	go(index + 1, selected + 1);
	
	// index 라는 값을 selected 번째로 선택하지 않았을 때	
	arr[selected] = 0;
	go(index + 1, selected);
}


// 강의 버전 (순서)
void seq(int index, int start){
	// 기저 사례 : 길이가 M 에 도달하면 종료
	if(index == M) {
		for(int i = 0; i < M; i++){
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}
	
	for(int i = start; i <= N; i++){
		if(used[i]) continue;
		
		arr[index] = i;
		
		used[i] = true;
		seq(index + 1, i + 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);
	
	go(1, 0);
}

해설

---

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

순서를 강제한다.

풀이

N과 M (1) 과 비슷한 문제였다. 

같은 방법으로, 재귀. 어떤 위치에서 올 수를 결정하는 것이라면, 변화하는 것을 살펴보자.

N과 M (1) 문제에서는 위치와 사용가능 한 수 가 바뀌었다면 이 문제에서는 하나가 추가된 것이다.

사용가능한 수의 시작 수(int start) 가 바뀐 것이다.

그렇다면, 문제를 해결하는 함수의 파라미터에 추가하여 논리를 전개해나가면 되겠다.

순서가 아닌 선택 에 대한 문제로 생각해보자.  N M 이 5 3 이라면, 5개 중에 3개를 선택하는것으로 볼 수 있겠다. 선택의 관점에서는 위치가 중요하지 않기 때문에, 중요한 것은 수이다.
그렇다면, 1 ~ N 의 수 중 각각의 수를 결정할 건지 하지 않을 건지 결정하는 문제라고 생각할 수 있다. 이런 논리로 문제풀이를 전개해나갈 때 필요한 것은 현재 선택한 수의 개수 일 것이다.
위 코드의 go 함수를 보면 이해할 수 있다.

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

- 이거인거 같은데? 라는 가벼운 검증도 없이 채점에 넣어본 부분이 아쉽다.

- 강의에서의 재귀에 대한 정의가 인상깊었다. 어떤 위치에서 올 수를 결정하는 것. 위치에 관계없이 그것이 성립해야하는 것.

위치가 바뀔 때 변화하는 것을 찾아내어 그것을 함수의 파라미터로 사용하는 것이다.

- 또한, used 배열. 사용한지 아닌지에 대한 배열은 쓸모가 없다는 것을 파악했어야 했다.