[BOJ/C++] 백준 15656번: N과 M (7)

Introduction

---

15656번: N과 M (7)

 

오늘 풀어볼 문제는 백준 15656번, N과 M (7)입니다. 자연수 N과 M이 주어질 때, N개의 서로 다른 자연수 중 중복을 허용하며 M개를 선택해 수열을 만들어야 합니다. 중복을 허용하기 때문에 visited(or selected) 배열이나 vector를 선언할 필요는 없는 게 주요 포인트입니다.

 

입력	→ 첫째 줄에 N과 M이 주어진다 ($1 \leq M \leq N \leq 7$) → 둘째 줄에 N개의 수가 주어진다. (input num $\leq 10,000$)
조건	→ N개의 자연수 중에서 M개를 고른 수열 → 같은 수를 여러 번 골라도 됨
출력	→ 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. → 중복되는 수열을 여러 번 출력하면 안된다. → 각 수열은 공백으로 구분해서 출력해야 한다. → 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

이제 본격적으로 문제를 풀어보도록 하겠습니다. 글의 순서는 이번에는 source code를 먼저 보고, 어떤 사고의 흐름으로 계획을 짰는지 Pseudo code를 통해 살펴보겠습니다. 그리고 ChatGPT에게 이번 문제를 풀어보게 할 예정입니다. Source code를 보고 싶어서 들어오신 분들을 위해서 순서를 조금 바꾸었습니다.

 

Source Code

---

/**
 * @file q15656.cpp
 * @author YoungJ-Baek (qordudwls1@gmail.com)
 * @brief solution for BOJ #15656, https://www.acmicpc.net/problem/15656
 * @version 0.1
 * @date 2023-03-10
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <algorithm>
#include <iostream>
#include <vector>

#define MAX 9

using namespace std;

int N, M;
int input[MAX];
vector<int> output;

void dfs(int count);

int main() {
  cin >> N >> M;
  for (int index = 0; index < N; index++) cin >> input[index];
  sort(input, input + N);
  dfs(0);
  return 0;
}

void dfs(int count) {
  if (count == M) {
    for (int index = 0; index < M; index++) cout << output[index] << ' ';
    cout << '\n';
  } else {
    for (int index = 0; index < N; index++) {
      output.push_back(input[index]);
      dfs(count + 1);
      output.pop_back();
    }
  }
}

 

Planning

---

 

ChatGPT

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void combinations(vector<int>& nums, int m, vector<int>& cur) {
    if (cur.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << cur[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        cur.push_back(nums[i]);
        combinations(nums, m, cur);
        cur.pop_back();
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    sort(nums.begin(), nums.end()); // sort the numbers to print in lexicographically increasing order

    vector<int> cur;
    combinations(nums, m, cur);

    return 0;
}

 

이번 문제에서 ChatGPT의 타율이 좋지 못했습니다. 우선 첫 번째로 생성한 코드의 경우 시간 초과나 메모리 초과가 아닌 오답을 내놨는데요. 문제 내용 중 가장 중요한 중복 허용을 이해하지 못하는 모습이었습니다. 그래서 이전 문제에서 사용했던 start 변수를 DFS 함수 안에서 사용했습니다. 이 부분을 아래와 같이 지적해 주었더니 실수를 인지하더군요. (귀찮아서 코테 문제는 한글로 물어봤습니다.. 그래서 지적 사항에도 한글과 영어를 혼용했습니다.)

 

[YoungJ]
I think 같은 수를 고를 수 있다 doesn't need start parameter in combination function

[ChatGPT]
You're right, the 'start' parameter is not necessary in this case since we are allowed to choose the same number multiple times. The code can be simplified by removing the 'start' parameter and the loop variable 'i' can always start from 0. Here's the updated code:

 

이 대화의 결과물이 바로 위에서 보여드린 코드입니다. 다만 한 부분이 실제 생성된 코드랑 다른데요. 실제로 생성한 코드에서는 '\n' 대신에 'endl'을 사용했습니다. 그래서인지 시간 초과로 실패하고 말았죠. 이전 문제에서는 크게 문제가 되지는 않고 통과했었는데요. 아마 이번 문제에서 사용된 Test Case들의 양과 질이 좋아서 그런 것으로 보입니다. 실제로 이전 문제에서는 0ms로 측정되던 제 코드의 source code 역시 이번 문제에서는 676ms로 증가함을 볼 수 있었습니다. 이렇게 증가한 Test Case에 'endl'으로 인한 추가 Overhead가 생기면 시간 초과로 실패할 수 있겠죠? 그래서 해당 부분을 수정해 주었더니 문제없이 통과함을 볼 수 있습니다.

다만 이를 눈치채기 전에 시간 초과로 혼낸(?) 다음 다시 생성하게 했더니 역시 못한다는 말은 못하는 ChatGPT는 답을 주었습니다. 틀린 답을 말이죠. 처음 보는 형태의 코드를 생성했으며, 이는 당연히(?) 틀렸습니다. 이로서 우리는 정답에 매우 근접한 답변에서의 미세 오차는 인간의 영역에 가깝지 않을까 추측할 수 있습니다 (사견입니다). 물론 정성을 들여서 질문을 했다면 답을 잘 생성할 수 있겠지만, 코드를 한 번 읽어보고 최적화를 해주는 것이 더 빨라 보이네요. 이제부터는 처음부터 문제를 줄 때 '\n'을 개행문자로 사용하라는 조건을 줘야겠습니다. 아래는 각각의 코드에 대한 채점 결과입니다.

 

아래부터 my source code, 첫 번째 생성답, 두 번째 생성답 w/ endl, 수정본 w/ \n, 틀리게 재생성한 답

 

Reference

---

GitHub - YoungJ-Baek/algorithm-study