찰떡개발자 코딩

1). 문제 : https://www.acmicpc.net/problem/15651

2). 풀이 : 

기존에 N과 M 1,2를 풀었다면 쉽게 풀수있을것이다.

기존에는 중복되지 않는 숫자의 조합으로 순열을 만드는것이었는데,

이번에는 숫자의 중복이 가능하다.

그렇다면 visited의 역할이 사라진다고 볼수있는것!!!ㅎㅎ

코드를 보자

일단 기존 코드에서 visited만 없앴는데 시간초과가 떠서, 

StringBuilder로 변경하고

int[] arr에 값을 넣어주는 for문을 없앤뒤 permute(); 안에서 arr[i]에 값을 넣어주었다.

이생각을 왜 처음부터 못했지..;ㅎㅎ

static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());


		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] arr = new int[N];
		int[] output = new int[N];

		permute(arr, output, 0, M);
		System.out.println(sb);
	}

	static void permute(int[] arr, int[] output, int depth, int cnt) {
		if(depth == cnt) {
			print(output,cnt);
			return;
		}

		for (int i = 0; i < arr.length; i++) {
			arr[i] = i+1;
			output[depth] = arr[i];
			permute(arr, output, depth+1, cnt);
		}
	}

	static void print(int[] output, int cnt) {
		for (int i = 0; i < cnt; i++) {
			sb.append(output[i]+" ");
		}
		sb.append("\n");
	}