[Baekjoon] 15652번: N과 M (4)

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

---

 

문제 해결 과정

착안

1부터 \(N\)까지의 자연수를 중복을 허용하되, 비내림차순을 만족하는 순서로 뽑아 수열을 만든다. 따라서 다음 항을 구하는 함수를 실행할 때, 현재 항보다 큰 숫자로만 구할 수 있도록 조건문을 추가하고자 하였다. 이후, 수열의 길이가 \(M\)이 될 때까지 재귀를 통해 수열을 만들고 길이가 \(M\)이 되면 출력한다.

 

구현

이전 포스트의 코드와 대부분 유사하여 이전 포스트의 코드를 수정하여 문제를 해결하였다. 중복된 수를 다시 뽑는 것이 가능하므로, Visited 여부를 확인할 필요가 없기 때문에 관련 코드를 지우고, 비내림차순으로 수열을 만들기 위한 조건문을 추가하였다.

 

한편, 표준 입출력 스트림의 입출력 속도를 최적화하여(사용 방법 및 주의점 관련 글) 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

class SequenceGenerator
{
public:
	SequenceGenerator(int n, int m) : N(n), M(m) {}

	void PrintSequence()
	{
		for (int i = 0; i < M - 1; i++)
			cout << Sequence[i] << " ";

		cout << Sequence[M - 1] << "\n";
	}

	void NextTerm(int num, int term)
	{
		Sequence[term++ - 1] = num;

		if (term > M)
		{
			PrintSequence();
			return;
		}

		for (int i = 1; i <= N; i++)
			NextTerm(i, term);
	}

	void FindSequences()
	{
		for (int i = 1; i <= N; i++)
			NextTerm(i, 1);
	}

private:
	const int N, M;
	int Sequence[7] = { 0, };
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M;
	cin >> N >> M;

	SequenceGenerator seq(N, M);
	seq.FindSequences();

	return 0;
}

 

실행 결과