백준 : 15650번 N과 M(2) (c++)

백준 링크

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

15650번: N과 M (2)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	61427	45806	32986	73.963%

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 3
2 4
3 4

예제 입력 3

4 4

예제 출력 3

1 2 3 4

코드 풀이

이전 문제인 N과 M(1)의 코드와 동일한데 중간에 추가한 부분이 있다.

 

문제의 설명을 기존 문제에서 고른 수열은 오름차순이어야 한다. 라는 조건이 추가가 되었다

그래서 J라는 변수를 선언하고 J가 0이 아닐 때 J = Array[K - 1] + 1이라는 값을 대입해 준다

위의 코드를 추가하면 오름차순 출력이 가능하게 된다.

 

예를 들어 J라는 변수를 추가 안 하고 for문 i에 i = K + 1이라는 값으로 선언을 하게 된다면

Array[0]이 2인숫자까지는 가능하겠지만 3이 되는순간부터 잘못된 값을 출력하게 된다.

정답인 코드를 작성하게 되면 Array[0]이 3일 때 Array[1]은 자동으로 이전 값 + 1부터 탐색이 진행되기 때문에

오름차순이 출력이 되는 것이다.

코드

#include <iostream>

using namespace std;

int N, M;
int Array[9];
bool Visit[9];

void Func(int K)
{
	if (K == M)
	{
		for (int i = 0; i < M; ++i)
		{
			cout << Array[i] << ' ';
		}

		cout << '\n';

		return;
	}

	// 
	int J = 1;

	if (K != 0)
		J = Array[K - 1] + 1;

	for (int i = J; i <= N; ++i)
	{
		// 해당 값이 사용 안했어야 가능
		if (!Visit[i])
		{
			Visit[i] = true;
			Array[K] = i;
			Func(K + 1);
			Visit[i] = false;
		}
	}
}


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

	Func(0);

	return 0;
}

 

N과 M(1) 링크

https://tin9-d-d-blog.tistory.com/216

백준 : 15649번 : N과 M(1) (c++)