[BOJ] N과 M (1) ~ (8)

https://www.acmicpc.net/search#q=n%EA%B3%BC%20m&c=Problems

 

 

[15649] N과 M (1)

- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

input

 

4 2

output

 

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

 

소스코드

 

import java.util.Scanner;

public class Main {

 	// main function
	make_permutation(0, n, m);
        
	public void make_permutation(int idx, int n, int m) {
		if (idx == m) {
			print(a, m);
			return;
		}
		for (int i = 1; i <= n; i++) {
			if (c[i]) continue;	// 중복 없이
			c[i] = true; a[idx] = i;
			make_permutation(idx + 1, n, m);
			c[i] = false;
		}
	}
}

 

[15650] N과 M (2)

- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

- 고른 수열은 오름 차순이어야 한다.

- make_permutation() 호출시 (직전에 사용한 수+1) 호출

 

 

input

 

4 2

 

output

 

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

 

 

소스코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
 
 	// main function
	make_permutation(0, 1, answer);

	public void make_permutation(int count, int start, int[] answer) {
		if (count == m) {
			print(answer);
			return;
		}

		for (int i = start; i <= n; i++) {
			answer[count] = i;
			make_permutation(count + 1, i+1, answer); // 중복(x), 오름차순(o)
		}
	}
}

 

[15651] N과 M (3)

- 1부터 N까지 자연수 중에서 M개를 고른 수열

- 같은 수를 여러 번 골라도 된다. // c 배열이나, start 변수 사용 x

 

 

input

 

4 2

 

output

 

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

 

 

 

소스 코드

 

import java.util.Scanner;

public class Main {
    // main function
    make_permutation(0, n, m));

	public void make_permutation(int idx, int n, int m) {
		if (idx == m) {
			for (int i = 0; i < m; i++) {
				sb.append(a[i] + " ");
			}
			sb.append("\n");
            return;
		} 
			for (int i = 1; i <= n; i++) {
				a[idx] = i;
				make_permutation(idx + 1, n, m);
			}
	}
}

 

 

[15652] N과 M (4)

- 1부터 N까지 자연수 중에서 M개를 고른 수열

- 같은 수를 여러 번 골라도 된다.

- 고른 수열은 비내림차순이어야 한다(오름차순) // start 변수 사용

 

 

input

 

4 2

 

 

output

 

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

 

 

소스코드

 

import java.util.Scanner;

public class Main {
	int[] a;
	int n, m;
	boolean[] c;

	// main function
    make_permutation(0, 1);
	
    }

	public void make_permutation(int count, int start) {
		if (count == m) {
			print(a);
			return;
		}

		for (int i = start; i <= n; i++) {
			a[count] = i;
			bf(count + 1, i);	// 중복(o) 오름차순(o)
		}
	}
}

 

 

[15654] N과 M (5)

- N개의 자연수 중에서 M개를 고른 수열

- 1~N 사이의 수열이 아닌 주어진 배열의 수열

 

 

input

 

4 2
9 8 7 1

 

 

output

 

1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8

 

소스코드

 

public class Main {
	int[] a;
	int n, m;
	boolean[] c;

		// main function
		int[] answer = new int[m];
		Arrays.sort(a);
        
		make_permutation(0, answer);
	}

	public void bf(int count, int[] answer) {
		if (count == m) {
			print(answer);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (!c[a[i]]) {
				c[a[i]] = true;
				answer[count] = a[i];
				bf(count+1, answer);
				c[a[i]] = false;
			}
		}
	}

 

 

[15655] N과 M (6)

- N개의 자연수 중에서 M개를 고른 수열

- 고른 수열은 오름차순이어야 한다. // 중복 없음, start 변수 사용

 

 

input

 

4 2
9 8 7 1

 

output

 

1 7
1 8
1 9
7 8
7 9
8 9

 

소스코드

 

public class Main {
	int[] a;
	int n, m;
	boolean[] c;

		// main function
		int[] answer = new int[m];
		Arrays.sort(a);
        
		make_permutation(0, 0, answer);
	}

	public void (int count,int start, int[] answer) {
		if (count == m) {
			print(answer);
			return;
		}

		for (int i = start; i < n; i++) {
			if(!c[a[i]]) {
				c[a[i]] = true;
				answer[count] = a[i];
				bf(count+1,i, answer);
				c[a[i]] = false;
			}
		}
	}

 

 

[15656] N과 M (7)

- N개의 자연수 중에서 M개를 고른 수열

- 같은 수를 여러 번 골라도 된다. // 중복 허용, 오름차순 x

 

 

 

input

 

4 2
9 8 7 1

 

output

 

1 1
1 7
1 8
1 9
7 1
7 7
7 8
7 9
8 1
8 7
8 8
8 9
9 1
9 7
9 8
9 9

 

소스코드

 

public class Main {
	int[] a;
	int n, m;
	boolean[] c;

		// main function
		int[] answer = new int[m];
		Arrays.sort(a);
        
		make_permutation(0, 0, answer);
	}

	public void (int count, int start, int[] answer) {
		if (count == m) {
			print(answer);
			return;
		}

		for (int i = 0; i < n; i++) {
			answer[count] = a[i];
			bf(count + 1, i, answer);
		}
	}

 

 

[15657] N과 M (8)

- N개의 자연수 중에서 M개를 고른 수열

- 같은 수를 여러 번 골라도 된다.

- 고른 수열은 비내림차순이어야 한다

 

 

input

 

4 2
9 8 7 1

 

output

 

1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9

 

소스코드

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	int[] a;
	int n, m;
	boolean[] c;
	StringBuffer sb = new StringBuffer();
	public void go() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		a = new int[n];
		c = new boolean[10001];

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		int[] answer = new int[m];
		Arrays.sort(a);
		make_permutation(0, 0, answer);
		System.out.println(sb);
	}

	public void make_permutation(int count, int start, int[] answer) {
		if (count == m) {
			for(int i = 0; i<m; i++)
				sb.append(answer[i]+" ");
			sb.append('\n');
			return;
		}

		for (int i = start; i < n; i++) {
			answer[count] = a[i];
			make_permutation(count + 1, i, answer);
		}
	}

	public void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}