[백준 15650] N과 M (2)

15650번: N과 M (2) (acmicpc.net)

15650번: N과 M (2)

 

 

배운것

- N과 M (1) 같은 경우에는 오름차순으로 싹다 뽑으면 되니까 for문 돌릴 때 그냥 i=0부터 신경쓰지 않아도 되었는데

N과 M (2)의 경우 중복되면 안되고 ( {1,2,3} , {3,2,1} ) 오름차순이라서 i=0으로 놓으면 안됨

그래서 시작 변수를 만들어줘서 임의로 변경을 시켜줌

 

- 순열과 조합

 

 

정답 코드 1

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

 

정답 코드 2 - next_permutation 이용

// http://boj.kr/5378d116242244a38cd2d7fc28d8678d
#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> a;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> M;
  // M의 개수만큼 0을 넣어줌
  for(int i = 0; i < N; ++i)  a.push_back(i < M ? 0 : 1);
  do{
    for(int i = 0; i < N; ++i)
      if(a[i] == 0) cout << i+1 << ' ';
    cout << '\n';
  }while(next_permutation(a.begin(), a.end()));
}