15663 N과 M(9) (C++)

이 문제는 그 동안의 문제들과는 조금 다른 결의 문제였다.

뭐 구동되는건 똑같지만, 다른점이라면 먼저 나왔던 수열은 중복 되면 안된다라는 것이었다.

 

이것에 대한 해답은 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

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

void func(int k) {
    if(k == m) {
		 for(int i = 0; i < m; i++) {
            cout << arr[i] << ' ';
        }
        cout << endl;
        return; // 리턴을 해서 바로 윗 단계로 올라감
	}
	int tmp = 0;
	for(int i = 0; i < n; i++) {
        if(!isused[i] && board[i] != tmp) { // 아직 사용되지 않은 경우
            arr[k] = board[i];
			tmp = board[i];
            isused[i] = 1;
            func(k+1);
			isused[i] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
	
	for(int i = 0; i < n; i++) {
		cin >> board[i];
	}
	sort(board,board+n);
    func(0);
	
}

중간에 보면 for문 안에 조건문이 존재하는데, 바로 board[]의 현재 배열과 미리 저장해놨던 전 배열과 같지 않을 경우 백트래킹을 허용한다는 조건이다.

간단히 생각해보면, 바로 직전의 배열의 수의 마지막 항이 같은지 확인하면 된다! (라는데.. 공부좀 더 해야겠다)

그리고 이 코드는 sort() 함수. 그러니까 사전순으로 정렬된 수여야만 구동이 가능하다. 다른방법의 문제면..다시 생각해봐야지 뭐..