백준, BOJ, 15649번 C++ [CPP] **

나 이거 맞았길래 봤더니

파이썬으로 풀었음 ㅎ

파이썬 permutation으로 3초만에 풀었음..ㅎ

C++로 해보자꾸나..

 

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

15649번: N과 M (1)

 

 

---

 

이 문제는 백트래킹이라는 원리를 적용해서 푼다.

 

코드에 주석을 보면서 이해해보자

 

#include<iostream>
#include<vector>

using namespace std;


int n,m;
///////////////////////////////////////
int arr[10]; // 선택에 쓰일 배열
bool isused[10]; // 사용여부

void func(int k){ // 현재 k개까지 수를 택했음   *1
  if(k == m){ // m개를 모두 택했으면
    for(int i = 0; i < m; i++)
      cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
    cout << '\n';
    return;
  }

  for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
    if(!isused[i]){ // 아직 i가 사용되지 않았으면
      arr[k] = i; // k번째 수를 i로 정함
      isused[i] = 1; // i를 사용되었다고 표시
      func(k+1); // 다음 수를 정하러 한 단계 더 들어감  *2
      isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함*3
    }
  }
}

///////////////////////////////////////////////

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

 

내가 *표 친 것이 3개 있다.

1번부터 보자

이 함수는 선택을 위해서 만들어진 것으로 0개가 선택된 상태로부터 출발한다.

 

2번을 보자

선택을 했으니 그 다음 차례에 선택할 것을 찾으러 다시 func에 들어가는 것이다.

 

3번을 보자

이미 선택되어 고르고 출력한다음 나온 것이다. 

함수가 return되어 종료되었으니 이 라인의 코드를 읽을 수 있는 것이다.

이 라인의 코드를 읽음으로써 나는 n+1 번째에 해당 선택지를 썼고

다른 위치의 선택지에서 쓰이기 위해 false 처리했다라는 뜻이다.

 

사실 정확하게는 이해 못했지만 다른 문제를 풀어서 이해해야 할 성 싶다.