JArchive 프로그래밍 일기

문제

N과M(9) 백준 15663

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int num[10];
int arr[10];
bool check[10];

void func(int cnt){ // 이전 수열의 마지막항과 새로 추가할 값이 같으면 중복된 수열이다.
  if(cnt == m){
    for(int i = 0; i < m; i++){
      cout << num[i]<< ' ';
    }
    cout << '\n';
    return;
  }

  int prev_num = -1;

  for(int i = 0; i < n; i++){ // 선택하여 출력할 수를 num에 저장
    if(!check[i] && prev_num != arr[i]){
      check[i] = true;
      num[cnt] = arr[i]; // cnt 번째 숫자를 i로 정한다.
      prev_num = arr[i]; // 방금 선택한 수를 기억해둔다.
      func(cnt+1); // 다음 숫자 탐색 시작
      check[i] = false;
    }
  }
}

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

  cin >> n >> m;
  for(int i = 0; i <n; i++){
    cin >> arr[i]; // 주어진 수를 arr에 저장
  }

  sort(arr, arr+n); // 정렬. 사전순으로 출력해야하기 때문.
  func(0); // 0번째 수를 선택하는 것으로 시작한다
  return 0;
}

리뷰

백트래킹에 익숙해지기 위한 문제 중 하나다.
수열이 [ 9, 7, 9, 1] 이 주어져도 (1, 9)를 두 번 출력하면 안된다. 하지만 (9, 9)는 출력해야 한다.

일단 수열을 입력받자마자 정렬한다.
이전 선택 값이 현재 선택 값과는 달라야 한다.
그래서 prev_num 변수를 쓴다.

처음에 prev_num 변수를 전역변수로 사용해서 틀렸다.
for문 내부의 함수의 재귀호출이 끝나면 check배열을 false로 돌려놓고, 다음 i번째 숫자를 검사하게 된다.
따라서 방금 종료된 재귀 호출에서 변경된 prev_num이 그대로 적용된다는 문제가 있다.
그래서 동일한 순서(cnt)의 숫자를 선택할 때는 prev_num을 똑같이 바라봐야 한다.
따라서 지역변수로 prev_num을 써야 한다.