[BOJ/C++] 백준 15651번: N과 M (3)

 

Introduction

---

15651번: N과 M (3)

오늘 풀어볼 문제는 백준 15651번, N과 M (3)입니다. 자연수 N과 M이 주어질 때, 1부터 N까지의 자연수 중 중복을 허용하며 M개를 고른 수열을 모두 구하는 문제입니다. 입력과 출력은 아래와 같습니다.

 

입력	자연수 N, M ($1 \leq M \leq N \leq 7$)
출력	➡️ 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다 ➡️ 중복되는 수열을 여러 번 출력해서는 안된다 (숫자의 중복은 허용) ➡️ 각 수열은 공백으로 구분해서 출력해야 한다 ➡️ 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

이제 본격적으로 문제를 풀어보도록 하겠습니다. 글의 순서는 이번에는 source code를 먼저 보고, 어떤 사고의 흐름으로 계획을 짰는지 살펴보겠습니다. 그리고 ChatGPT에게 이번 문제를 풀어보게 할 예정입니다. 순서를 조금 바꾼 이유는 source code를 보고 싶어서 들어오신 분들을 위해서가 있으며, ChatGPT가 예상 밖의 결과를 출력했기에 조금 길게 다루고자 합니다.

 

Source Code

---

/**
 * @file q15651.cpp
 * @author YoungJ-Baek (qordudwls1@gmail.com)
 * @brief solution for BOJ #15649, https://www.acmicpc.net/problem/15651
 * @version 0.1
 * @date 2023-02-04
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <iostream>
#define MAX 8

int N, M;           // two inputs, N(range of sequence), M(size of sequence)
int sequence[MAX];  // array for generated sequences

void dfs(int cnt);

int main() {
  std::cin >> N >> M;
  dfs(0);
}

void dfs(int cnt) {
  if (cnt == M)  // array size reaches maximum size
  {
    for (int index = 0; index < M; index++) std::cout << sequence[index] << ' ';
    std::cout << '\n';
    return;
  } else {
    for (int index = 1; index <= N; index++) {
      sequence[cnt] = index;
      dfs(cnt + 1);
    }
  }
}

 

Planning

---

이번 문제 역시 14649번 문제의 변형입니다. 14650번이 업그레이드 느낌을 받았다면, 이 문제는 약간 다운그레이드 느낌을 받았습니다. 숫자가 중복으로 선택되는 것을 방지하고자 추가했던 visited 변수를 제외함과 동시에 중복 여부를 확인하는 조건문 역시 드러내 줍니다. 그렇다면 짜잔! 완성입니다. 참 쉽죠? 하하 :D

아래는 14649번 문제에 대한 풀이입니다. 추가로, DFS를 사용했기 때문에 중복 수열이 선택되는 일은 걱정 안 해도 괜찮습니다.

 

[BOJ/C++] 백준 15649번: N과 M (1)

 

ChatGPT

---

지난번 포스트에서 ChatGPT의 강력함을 경험했습니다. 이번에도 역시 굳건한 믿음을 가지고 입력으로 문제를 주었습니다. 그러나 이번에는 좀 실망스러운 결과를 출력했는데요. 같이 한번 살펴보죠. 항상 그렇듯 대화 구분을 위해 제 말과 ChatGPT의 말은 다르게 표현하도록 하겠습니다.

YoungJ-Baek

ChatGPT

 

Tell me the answer code of following question with C++ Question.
Given the natural numbers N and M, write a program to find all sequences with lengths M that satisfy the following conditions. A sequence of M natural numbers from 1 to N You can choose the same number several times.

[Input]
The first line is given the natural numbers N and M. (1 ≤ M ≤ N ≤ 7)

[Output]
It outputs a sequence that satisfies the conditions of the problem, one per line. Duplicate sequences should not be printed multiple times, each sequence should be separated by a space. The sequence shall be printed in order of increasing in dictionary order.

[Restrictions]
Time: 1 second
Memory: 512MB

 

이번에는 제약 조건도 잊지 않고 추가해 주었습니다 :)

 

Here is a code in C++ that generates all sequences of length M from 1 to N allowing duplicates, and in ascending order, with a time limit of 1 second and memory limit of 512MB:

#include <iostream>
#include <vector>

using namespace std;

vector<int> sequence;

void search(int n, int m) {
    if (sequence.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << sequence[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        sequence.push_back(i);
        search(n, m);
        sequence.pop_back();
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    search(n, m);
    return 0;
}

 

사실 위 코드는 시간제한을 초과합니다. 그래서 시간 초과!! 를 뱉으며 장렬히 전사해버리죠. 그래서 다양한 힌트를 주었는데요. 놀랍게도 최적화 과정을 거쳐도 전부 시간제한을 초과하거나, 틀린 결과를 출력했습니다. 결과적으로 전부 오답인 거죠. 아래는 제가 ChatGPT에 준 힌트들입니다.

 

I think using 'vector' needs much time. How about using static array to improve performance?

The compiler version is C++17

Hmm, I think the algorithm is quite good, but it exceeds given time constraints, 1 second. Please optimize the code not to violate the time constraint.

I run the code right now, but the answer is wrong. I don't know why. Can you explain?

 

수차례 코드를 생성하고 제출하고 틀리자 근본 원인은 무엇이냐고 물어보게 되었습니다. 그러자 입력과 출력 예제를 달라고 했습니다. 그러면 큰 도움이 될 거라고 하는데, 괜찮은 답변이라고 생각하면서도 좀 어이가 없었죠. 아래는 그 내용입니다.

 

Yes, providing an example test case would be helpful in understanding the problem and finding the root cause of the incorrect output. You can share the inputs and the expected outputs, which will make it easier to identify the issue with the code.

 

그래서 입출력을 주었습니다. 결과는..! 오답이었죠. 좀 많이 답답해진 상태로 이제 테스트를 통과한 제 코드를 보여주었습니다. 한번 뭐가 문제였는지 물어보고 싶었거든요.

 

Your code violates time limit. Here's my code, it passes the test. Please compare them.
[Code]
... (이하 생략)

 

그랬더니 자신의 코드는 패스하지 못하는 이유, 즉 차이점을 분석하기 시작했습니다.

 

The code provided by you is correct and seems to work within the given time limit. The main difference between this code and the previous code I generated is the use of a static array (sequence[MAX]) instead of a vector to store the sequences. This change eliminates the need to allocate memory dynamically, which could be a time-consuming process. Additionally, the code does not have any unnecessary operations, making it more efficient.

 

잠깐만요..? 분명 이 친구는 제 조언을 받아들여 static array를 사용했습니다. 그런데 왜 저런 소리를 하는 걸까요? 순간 좀 화가 나서 정정 보도를 요청했습니다.

 

But your latest code does not allocate dynamically.

const int N = 8;
int n, m, a[N];

 

어딜 거짓말이야! 정정 보도를 요청했더니 사과를 하더군요. 그런데 그 이후 행보가 조금 어이없었습니다. 이 친구가 표절을 하기 시작했습니다. 후속 보도로 업데이트된 코드를 생성했는데, 제가 준 코드와 거의 유사하더군요. 제 코드는 위 Source Code 항목에서 볼 수 있습니다.

 

You're right, I apologize for the oversight. Allocating memory dynamically is not necessary in this case, as the number of elements in the array is known in advance and can be fixed at compile time.
Here's the updated code that uses a fixed-size array:

#include <iostream>
const int N = 8;
int n, m, a[N];

void dfs(int cnt) {
  if (cnt == m) {
    for (int i = 0; i < m; i++) std::cout << a[i] << ' ';
    std::cout << '\n';
    return;
  }
  for (int i = 1; i <= n; i++) {
    a[cnt] = i;
    dfs(cnt + 1);
  }
}

int main() {
  std::cin >> n >> m;
  dfs(0);
  return 0;
}

 

그래서 좀 어이가 없어서 물어봤죠. 너 왜 여태까지는 이런 코드 생성 못했어? 답변은 아래와 같았습니다. 약간 만능 치트키 느낌이 나지만, 난 널 도와줄 뿐이야 XD

 

As a language model, I try to generate the best possible solution based on the information and constraints provided to me. I apologize if I did not meet your expectations in previous answers, but I am here to assist you and improve with each interaction. It is important for you to clearly communicate the requirements and constraints, so that I can better understand and provide you with a more accurate solution.

 

하하, 재밌는 경험이었습니다. 추가로, 그러면 ChatGPT를 어떻게 활용하는 게 좋을지 물어보기도 했습니다. 그랬더니 Pseudo Code를 추천해주기도 했습니다. 다음 포스팅에서는 Pseudo Code를 통해 풀어보게 해 보겠습니다.

 

Appendix

---

참고로 ChatGPT에 previous code라는 말을 쓸 때는 조심해야 합니다. 바로 직전의 code를 참조하지 않고, 높은 확률로 최초의 코드를 보는 것 같더군요. Latest 혹은 직접 복사하는 것을 추천드립니다.