[BOJ] 15650번 : N과 M (2)

1. problem :

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int N, M; 
int ans[8];
int isUsed[8] = { 0 };
int temp = -1; // k = 0일때 비교를 위해 설정;
void backtrack(int k,int temp) {
	if (k == M) {
		for (int i = 0; i < M; i++) {
			cout << ans[i] << ' ';
		}
		cout << '\n'; 
		return;
	}
	for (int i = 0; i < N; i++) {
		if (!isUsed[i] && i + 1 > temp) {
			isUsed[i] = 1; 
			ans[k] = i + 1; 
			backtrack(k + 1,i+1); 
			isUsed[i] = 0;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;

	backtrack(0,0);
}

오름차순만 출력하기 위해, 매개변수를 하나 더 설정하고, 비교하는 과정을 진행하였다. 

 

3. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/2a245058ecd74055bf168363740139a4
#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[10];
bool isused[10];

void func(int k){ // 현재 k개까지 수를 택했음.
  if(k == m){ // m개를 모두 택했으면
    for(int i = 0; i < m; i++)
      cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
    cout << '\n';
    return;
  }
  int st = 1; // 시작지점, k = 0일 때에는 st = 1
  if(k != 0) st = arr[k-1] + 1; // k != 0일 경우 st = arr[k-1]+1
  for(int i = st; i <= n; i++){ 
    if(!isused[i]){ // 아직 i가 사용되지 않았으면
      arr[k] = i; // k번째 수를 i로 정함
      isused[i] = 1; // i를 사용되었다고 표시
      func(k+1); // 다음 수를 정하러 한 단계 더 들어감
      isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
    }
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  func(0);
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0C/solutions/15650.cpp

basic-algo-lecture/0x0C/solutions/15650.cpp at master · encrypted-def/basic-algo-lecture

int st = 1; // k = 0일 때는 1부터 시작, 

int st = arr [k-1] + 1부터 시작 

꼭 외워야겠다. 이런 표현 방법을