[Baekjoon] 15651번: N과 M (3)

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

15651번: N과 M (3)

 

---

 

문제 해결 과정

착안

1부터 \(N\)까지의 자연수를 중복을 허용하여 뽑아 수열을 만든다. 만들어지는 모든 수열을 출력해야하므로 수열의 길이가 \(M\)이 될 때까지 재귀를 통해 수열을 만들고, 길이가 \(M\)이 되면 출력한다.

 

구현

이전 포스트의 코드와 대부분 유사하여 이전 포스트의 코드를 수정하여 문제를 해결하였다. 중복된 수를 다시 뽑는 것이 가능하므로, Visited 여부를 확인할 필요가 없기 때문에 관련 코드를 지우기만 하면 문제를 해결할 수 있었다(Visited 여부와 관련이 없으므로 굳이 trace back 하는 코드도 필요 없음).

* 조건문 연산을 살짝 줄이기 위해 일부 코드 수정하였음.

 

한편, 표준 입출력 스트림의 입출력 속도를 최적화하여(사용 방법 및 주의점 관련 글) 문제를 해결해보니 약간 더 빠른 실행 속도를 보였다(실행 결과 참고).

 

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

#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;
}

 

실행 결과

아래 결과: 이전 포스트에서 Visited 관련 코드만 제거하여 제출, 위 결과: 표준 입출력 스트림 입출력 속도 최적화