[BOJ/C++] 백준 15652번: N과 M (4)

Introduction

---

15652번: N과 M (4)

 

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

 

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

 

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

 

Source Code

---

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

using namespace std;

vector<int> result;
int N, M;

void dfs(int count, int start);

int main() {
  cin >> N >> M;
  dfs(0, 1);
  return 0;
}

void dfs(int count, int start) {
  if (count == M) {
    for (auto iter = result.begin(); iter != result.end(); iter++)
      cout << *iter << ' ';
    cout << '\n';
  } else {
    for (int index = start; index <= N; index++) {
      result.push_back(index);
      dfs(count + 1, index);
      result.pop_back();
    }
  }
}

 

Pseudo Code

---

// 전역 변수 선언
vector<int> result; // 결과 vector
int N, M;

void dfs(count, start)
{
	if(count == M) print 하고 종료;
    else
    {
    	for(index = start; index <=N; index++)
        {
        	result.push_back(index);
            dfs(count + 1, index);
            result.pop_back();
        }
    }
}

int main()
{
	N, M 입력;
    dfs(0, 0);
    return 0;
}

 

ChatGPT

---

#include <iostream>
#include <vector>
using namespace std;

void dfs(int n, int m, vector<int>& v) {
    if (m == 0) {
        for (int i = 0; i < v.size(); ++i) {
            cout << v[i] << ' ';
        }
        cout << '\n';
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (v.empty() || i >= v.back()) {
            v.push_back(i);
            dfs(n, m-1, v);
            v.pop_back();
        }
    }
}

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

    vector<int> v;
    dfs(n, m, v);

    return 0;
}

 

사실 ChatGPT가 짠 코드가 제가 가고자 하는 방향과 일맥상통합니다. 최대한 전역 변수 사용을 피하고 싶었고, 불필요한 변수 사용은 최대한 하지 않고 싶었습니다. 수열의 길이를 주어진 M을 활용해 표현했으며, 전역 변수는 일절 사용하지 않았습니다. 인간은 귀찮아서 하지 않는 부분을 정확히 짚어주니 참 유용한 것 같습니다.

 

Reference

---

GitHub - YoungJ-Baek/algorithm-study