[백준 / C언어] 15651번: N과 M (3)

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

15651번: N과 M (3)

 

난이도: solved.ac 실버 3

 

 

알고리즘 분류

---

백트래킹

 

문제 설명

---

1부터 N까지의 숫자를 중복 허용하여 M개 골라 나열하는 문제다

이때 나열된 수열은 총 N^M개가 된다

 

구현

---

출력할 수열을 배열 arr에 저장한다

1부터 N까지의 숫자를 for 문을 이용해 arr에 넣어주고 함수 NnM을 재귀 호출한다

NnM의 인수로 cnt라는 변수가 사용되는데, 이는 현재 배열에 저장된 수열의 길이를 의미한다

그리고 cnt가 M이 되는 시점, 즉 수열의 길이가 M이 되면 지금까지 배열에 저장된 수들을 출력한다

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int N, M;
int arr[7];
void NnM(int cnt);

int main() {
	scanf("%d %d", &N, &M);
	NnM(0);
	return 0;
}

void NnM(int cnt) {
	int i;
	if (cnt == M) {
		for (i = 0; i < M; i++)
			printf("%d ", arr[i]);
		printf("\n");
	}
	else {
		for (i = 1; i <= N; i++) {
			arr[cnt] = i;
			NnM(cnt + 1);
		}
	}
}