백준 15649

문제 분석

 

CPU가 1초에 대략 1억번 연산을 한다고 가정했을 때 시간제한 안에 돈다는 것을 확인할 수 있음

 

C++ 코드

#include<iostream>	
using namespace std;

// N, M은 1~8 사이의 값 
int N, M;

// N과 M이 8일때 최대 길이가 8칸이 나옴 상태는 인덱스 1부터 시작하게끔 설정하므로 크기를 더 늘려줌
int arr[10];
int state[10]; // 0(사용가능), 1(사용중)

void func(int k) {

	// 1. base condition(재귀 함수 탈출 조건)
	// M의 길이만큼 숫자가 모두 들어갔을 때 
	// ex) M=1 일때 숫자가 하나만 들어가면 탈출해야 됨
	if (k == M) {
		for (int i = 0; i < M; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}

	// 2. 재귀식
	// N만큼 반복문을 돌면서 사용가능한 숫자가 있는지 체크
	for (int i = 1; i <= N; i++) {
		if (state[i] == 0) {
			arr[k] = i;
			state[i] = 1;
			func(k + 1);
			state[i] = 0;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	// 1.입력	
	cin >> N >> M;

	// 2.로직
	// 최초 함수 인자값에 0을 넣는 이유는 배열에 인덱스 0부터 값이 들어가기 때문
	func(0);
	
	return 0;
}

 

 

Java 코드

import java.util.Scanner;

public class Main2 {	
	
	static int n,m;
	static boolean[] isUsed = new boolean[10]; // n개의 숫자들의 사용여부
	static int[] output = new int[10];
	
	public static void func(int k) { 
		// k의 뜻은 n이 m개 구성되었을 때 출력
		// m이 2라면 k(n)의 개수가 m만큼 들어간 경우 
		if(k == m) {
			for(int i=0;i<m;i++) {
				System.out.print(output[i] + " ");
			}
			return;
		}
		
		// n이 3이고 m이 3이라면 1,2,3 각각에 대해서 경우의 수가 생기므로 전체적으로 n번 반복하는 동안 그 n을 기준으로 m개가 구성될때 까지 n번 반복하게 된다 
		// n * (n-1)
		for(int i=1;i<=n;i++) {
			// isUsed[0] -> 1은 사용중인가?
			if(!isUsed[i]) {
				output[k] = i;
				isUsed[i] = true;
				// m이 2라면 두번째 칸(두번째 인덱스)에 들어갈 값을 찾기
				func(k+1);
				isUsed[i] = false;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		n = sc.nextInt();
		m = sc.nextInt();
		func(0);
	}

}