15656 N과M (7) (C++)

N과 M 시리즈 문제가 생각보다 재밌다. (뭐 잘 풀려서 그런거지..이러다가 안풀리면 재미없다고 한다 또)

 

아무튼. 이 문제는 

itlearning.tistory.com/entry/15651-N%EA%B3%BC-M3-C

15651 N과 M(3) (C++)

이 문제와 똑같다. 단지 수열을 내가 입력하는 것이 추가된 것 뿐.

 

그래서 이 문제의 답을 참고해서 코드를 작성했다.

 

문제의 해결법은 이렇다. 원하는 수열을 입력받고, 입력받은 수열을 배열에 저장한 뒤, 출력하는 수열을 따로 만들어서 복사시키고 출력하면 된다!

 

그리고 1부터 출력시키고 싶다면 모든 isused[]배열을 false로 초기화 시키고 출력하면 된다.

 

이해가 안간다면

itlearning.tistory.com/entry/15654-N%EA%B3%BCM-5-C

15654 N과M (5) (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; // 리턴을 해서 바로 윗 단계로 올라감
	}
	
	for(int i = 0; i < n; i++) {
        if(!isused[i]) { // 아직 사용되지 않은 경우
            arr[k] = board[i];
            isused[i+1] = 1;
            func(k+1);
			for(int i = 0; i < n; i++) {
				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문을 보면 arr에 우리가 입력한 수열을 입력시키고, 방문했다고 isused를 1(true)로 바꾼다.

 

그리고 재귀를 돌고, 이중 for문에서 isused를 전부 초기화 시킨다. 그렇게 되면 다시 처음 숫자부터 출력이 된다.