[Baekjoon/백준] 15651번: N과 M (3)(C/C++)

단계별로 풀어보기 14단계(백트래킹) 3번 문제

https://www.acmicpc.net/step/34

백트래킹 단계

---

백준 15651번: N과 M (3)

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

15651번: N과 M (3)

---

문제 설명

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

---

입력과 출력

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

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

---

접근 방법

이번 문제는 저번 문제들과 마찬가지로 자연수 N과 M을 입력받고, 1~N까지 범위 내에서 M개로 구성된 순열을 출력하는 문제다. 다만 이전과는 다르게 수열 구성에 자기 자신을 포함할 수 있도록 했다.

이전까지 중복을 방지한 것은 visited 배열을 사용해서 해당 인덱스 숫자에 방문했는지 하지 않았는지를 구분했다. 그러니까 중복을 허용하려면 이전 코드에서 visited 배열과 함께 if문 조건만 제거하면 해결할 수 있다.

---

코드

#include <stdio.h>
#define MAX 9

int arr[MAX] = { 0, };

void dfs(int N, int M, int count) {
	if (count == M) {
		for (int i = 0; i < M; i++)
			printf("%d ", arr[i]);
		printf("\n");
		return;
	}

	for (int i = 1; i <= N; i++) {
		arr[count] = i;
		dfs(N, M, count + 1);
	}
}

int main(int argc, char *argv[]) {
	int N, M;
	scanf("%d %d", &N, &M);

	dfs(N, M, 0);

	return 0;
}

---

결과

백준 제출 결과