[BOJ/C++] 백준 15657번: N과 M (8)

Introduction

---

오늘 풀어볼 문제는 백준 15657번, N과 M (8)입니다. 자연수 N과 M이 주어질 때, N개의 자연수 중 중복을 허용하며 비내림차순으로 M개를 고른 수열을 모두 구하는 문제입니다. 입력과 출력은 아래와 같습니다. 비내림차순은 이름 그대로 오름차순이 아닌 수열을 의미합니다. 모든 원소가 같아도 괜찮지만 작아지면 안 됩니다. 이를 염두에 두고 풀어보도록 하겠습니다.

 

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

 

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

 

Source Code

---

/**
 * @file q15657.cpp
 * @author YoungJ-Baek (qordudwls1@gmail.com)
 * @brief solution for BOJ #15657, https://www.acmicpc.net/problem/15657
 * @version 0.1
 * @date 2023-03-12
 *
 * @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 start);

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

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

 

Planning

---

 

• N개의 자연수는 모두 다른 수이기 때문에 Sorting을 통해 결과물이 사전 순으로 증가할 수 있게 합니다.
• 같은 수를 여러 번 골라도 되기 때문에 중복을 허용할 수 있도록 시작 지점을 증가시키지 않습니다.
• 비내림차순이기 때문에 재귀 함수의 시작 지점을 0부터가 아닌, 현재 지점부터 하도록 합니다.

 

ChatGPT

---

이번에는 Lesson-learn을 통해 'endl' 대신 '\n을 사용하라고 조언을 해주며 문제를 주었습니다.

[YoungJ]
generate a code of c++ that can solve the problem as follows (use '\n' instead of 'end' for line breaking):

(details..)

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

using namespace std;

void printSequence(const vector<int>& sequence) {
    for (int i = 0; i < sequence.size(); i++) {
        cout << sequence[i] << " ";
    }
    cout << "\n";
}

void generateSequence(int N, int M, vector<int>& sequence, int current, int count, const vector<int>& numbers) {
    if (count == M) {
        printSequence(sequence);
        return;
    }
    for (int i = current; i < N; i++) {
        sequence[count] = numbers[i];
        generateSequence(N, M, sequence, i, count + 1, numbers);
    }
}

int main() {
    int N, M;
    cin >> N >> M;

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

    sort(numbers.begin(), numbers.end());

    vector<int> sequence(M);
    // 1st try -> wrong, initial current value should be 0, not 1
    // generateSequence(N, M, sequence, 1, 0, numbers);
    
    // 2nd try
    generateSequence(N, M, sequence, 0, 0, numbers);

    return 0;
}

 

친절하게 아래처럼 해답에 대한 설명을 생성해줍니다. 그러나 처음 생성한 코드에는 오류가 있어 이 부분에 대해 혼내니 다시 고쳐서 생성해 주더군요. 치명적인 부분은 아니고 initial current value가 0이 아닌 1을 주었습니다.

 

[ChatGPT]
Explanation:
We start by reading the input values of N and M.
We then read the N natural numbers into a vector numbers and sort them in ascending order using sort.
We then define a helper function printSequence that prints a given sequence of numbers followed by a line break.
We define another helper function generateSequence that generates all valid sequences of length M that satisfy the given conditions, starting from the given current number and count number of elements already added to the sequence.
The base case for the recursive function is when count equals M, which means we have generated a complete valid sequence, so we print it using the printSequence function and return.
In the recursive case, we loop over all possible numbers starting from current and up to N. For each number, we add it to the sequence at index count, and then recursively call generateSequence with the new current value set to the current number, and increment count by 1.
In the main function, we define a vector sequence of size M, which will be used to store the generated sequences, and call the generateSequence function to start the generation process with initial current value of 1 and count of 0.

 

Reference

---

GitHub - YoungJ-Baek/algorithm-study