15654~15657_N과 M (5)~(8) (JAVA)

1d-1c/BOJ

15654~15657_N과 M (5)~(8) (JAVA)

yeon_11 2020. 11. 11. 19:05

15654_N과 M (5) : 순열

15654번: N과 M (5)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열

www.acmicpc.net

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;

public class Main {
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		int[] num = new int[N];
		boolean[] checked = new boolean[N];
		List<Integer> ans = new ArrayList<>();
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st2.nextToken());
		}
		Arrays.sort(num);

		permutation(num, ans, checked);
		System.out.print(sb);
	}
	private static void permutation(int[] num, List<Integer> ans, boolean[] checked){
		if(ans.size()==M){
			for(int i=0; i<ans.size(); i++){
				sb.append(ans.get(i)).append(" ");
			}
			sb.append('\n');
			return;
		}

		for(int i=0; i<num.length; i++){
			if(!checked[i]){
				checked[i] = true;
				ans.add(num[i]);
				permutation(num, ans, checked);

				checked[i] = false;
				ans.remove(ans.size()-1);
			}
		}
	}
}

15655_N과 M (6) : 조합

15655번: N과 M (6)

www.acmicpc.net

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int[] num = new int[N];
		int[] ans = new int[M];
		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st2.nextToken());
		}
		Arrays.sort(num);

		combination(num, ans, 0, 0, 0);
		System.out.print(sb);
	}
    
	private static void combination(int[] num, int[] ans, int num_index, int ans_index, int cnt){
		if(cnt == M){
			for(int i=0; i<ans.length; i++){
				sb.append(ans[i]).append(" ");
			}
			sb.append('\n');
			return;
		}
		if(num_index >= N)
			return;

		ans[ans_index] = num[num_index];
		combination(num, ans, num_index+1, ans_index+1, cnt+1);
		combination(num, ans, num_index+1, ans_index, cnt);
	}
}

15656_N과 M (7) : 중복 순열

15656번: N과 M (7)

www.acmicpc.net

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;

public class Main {
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int[] num = new int[N];
		List<Integer> ans = new ArrayList<>();
		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st2.nextToken());
		}
		Arrays.sort(num);

		permutation(num, ans);
		System.out.print(sb);
	}

	private static void permutation(int[] num, List<Integer> ans){
		if(ans.size() == M){
			for(int i=0; i<ans.size(); i++){
				sb.append(ans.get(i)).append(" ");
			}
			sb.append('\n');
			return;
		}

		for(int i=0; i<num.length; i++){
			ans.add(num[i]);
			permutation(num, ans);
			ans.remove(ans.size()-1);
		}
	}
}

15656_N과 M (8) : 중복 조합

15657번: N과 M (8)

www.acmicpc.net

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());

		StringTokenizer st2 = new StringTokenizer(br.readLine());
		int[] num = new int[N];
		int[] ans = new int[M];
		for(int i=0; i<N; i++){
			num[i] = Integer.parseInt(st2.nextToken());
		}
		Arrays.sort(num);

		combination(num, ans, 0, 0, 0);
		System.out.print(sb);
	}

	private static void combination(int[] num, int[] ans, int num_index, int ans_index, int cnt){
		if(cnt == M){
			for(int i=0; i<ans.length; i++){
				sb.append(ans[i]).append(" ");
			}
			sb.append('\n');
			return;
		}
		if(num_index >= N)
			return;

		ans[ans_index] = num[num_index];
		combination(num, ans, num_index, ans_index+1, cnt+1);
		combination(num, ans, num_index+1, ans_index, cnt);
	}
}

순열 nPr

① 순열 : 순서O, 중복X ('중복'은 자기자신 포함 여부를 의미) 예) 1,2,3,4 중 2개 뽑는 경우 (1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3) /* N : 총 숫자 개수(num.length)..

yeone2ee.tistory.com

조합 nCr

조합 : 순서X, 중복X ('중복'은 자기자신 포함 여부를 의미) 예) 1,2,3,4 중 2개 뽑는 경우 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) /* N : 총 숫자 개수(num.length) R : 숫자 중에서 뽑는 개수 (nCr에서 r을..

yeone2ee.tistory.com

저작자표시 비영리 변경금지

'1d-1c > BOJ' 카테고리의 다른 글

10819_차이를 최대로 (JAVA) (0)	2020.11.15
15663~15666_ N과 M (9)~(12) (JAVA) (0)	2020.11.13
15649~15652_N과 M (1)~(4) (JAVA) (0)	2020.11.11
4963_섬의 개수 (JAVA) (C++) (0)	2020.11.09
1182_부분수열의 합 (JAVA) (0)	2020.11.08

현재글15654~15657_N과 M (5)~(8) (JAVA)

백수연