15651 N과 M (3)

N과 M (3) (15651)

 

풀이코드

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

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);
}

 

해설

---

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

내가 이전에 비슷한 문제를 풀어본적이 있던가 ? -> 15649번

풀이

15649 번 문제와 같은 맥락을 가진다. 다른 점은 중복을 허용하느냐 안하느냐 이다. 이번 문제에서는 중복을 허용 했으므로 중복을 허용하지 않는 조건문을 주석 처리하여 해결했다.

 

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