[BOJ/15649/C++] N과 M(1)

SHark·2023년 2월 20일

BOJ

목록 보기

2/59

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성

조건

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

SOL

N,M이 주어지고, 1부터 N까지 자연수에서 중복없이 M개를 고른 수열을 뽑는 문제이다.
즉 , nPr의 모든 경우의 수를 출력해봐라라는 문제이다. 순열 구현할 줄 아느냐! 라고 물어보는 것과 같다.

순열을 구현하는 방법은 라이브러리를 이용하는 방법도 있고, 반복문도 있고, 재귀적인 방법을 이용하는 방법도 있다. 근데, 보통 반복문을 이용하면 3개를 뽑는다면 3중 반복문이 들어가는 형태로 구현이 되므로, M중 반복문은 적절한 형태가 아닌것 같다.

재귀적으로 구현을 해보자. 그리고, nPr을 구현하는 방법도 매우 많지만 나는 1부터 N까지 방문기록을 하고, 해제하는 형식으로 짤 것이다. 이게 더 로직이 이해하기 쉽고, 제일 나한테 와닿는 풀이이기 때문이다.

첫번째 풀이 (오답)

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

void PrintVector(vector<char> result)
{
  for (int i = 0; i < result.size(); i++)
  {
    cout << result[i] << " ";
  }
}
void Permutation(vector<int> arr, vector<char> result, vector<bool> used, int depth)
{
  if (depth == result.size()) // r일때
  {
    PrintVector(result);
    cout << "\n";
  }
  for (int i = 0; i < arr.size(); i++)
  {
    if (used[i] == true)
      continue;
    used[i] = true;
    result[i] = arr[i] + '0';
    Permutation(arr, result, used, depth + 1);
    used[i] = false;
  }
}
int main()
{
  int n, r;
  cin >> n >> r;
  // 배열 , 방문체크
  vector<int> arr(n);
  vector<bool> used(n);
  // 결과
  vector<char> result(r);

  // 1~N까지 배열 생성
  for (int i = 0; i < n; i++)
  {
    arr[i] = i + 1;
  }
  Permutation(arr, result, used, 0);
  return 0;
}

이유

i번째 result에 arr[i]를 담게되면, 출력부분에서 i번째를 출력해줘야합니다.
즉, 우리가 원하는 출력값을 얻으려면 depth의 값과 depth와 size가 같아졌을 때의 i값 2개가 더 필요하게 됩니다.(로직이 복잡해집니다) . 게다가, Vector이 유동배열이라서 다행이지, 사실 result[i] = arr[i] +'0' 이부분에서 OutofIndex가 나야 맞는겁니다.

두번째 수정

Depth번째에 i를 저장하면, 우리가 원하는 만큼 딱 출력하고 끝낼거라고 생각이 되었습니다.

result[i] = arr[i] + '0'을 result[depth] = arr[i] +0으로 수정하였습니다.

세번째 수정

위와 같이 수정했을 때, 값은 똑같이 나오지만, 쓸데없는 for이 돌게 됩니다. 예를들어, $3P2$ 일때, Depth가 2일때는 아래의 For문을 돌 필요가 없습니다. 물론 used로인해서 continue되고, Vector니까 영향을 받지않는 곳에 값이 저장될테지만, 어쨋든 For문이 쓸데없이 돌게 되는게 너무 불 -편했습니다. 그래서 , return으로 과감히 짤라줬습니다.

  if (depth == result.size()) // r일때
  {
    PrintVector(result);
    cout << "\n";
    return;  // return 문 추가로, 아래와 같이 Depth가 2일때는 
    아래의 반복문을 돌 필요가 없도록 바로 return해주기. 
  }

수정전

수정후