[백준 JAVA] N과 M(1~6)

재귀함수의 개념을 잡기 위해서 백준의 N과 M 문제를 1~6까지 풀어보았다.

재귀 개념이 부족하다면 아래 문제들을 풀어보는 것을 추천한다.

 

문제

---

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

15649번: N과 M (1)

 

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

15650번: N과 M (2)

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

15651번: N과 M (3)

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

15652번: N과 M (4)

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

15654번: N과 M (5)

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

15655번: N과 M (6)

풀이방법

---

순열 조합 구현 방법은 아래 링크에 정리되어있다.

 

https://sproutedpotato.tistory.com/65

순열, 조합

N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

해결방안

• 단순한 순열 코드이다.

import java.util.Scanner;

public class Main {

	static int N,C;
	static int num[];
	static boolean visit[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input=new Scanner(System.in);
		N=input.nextInt();
		C=input.nextInt();
		num=new int[C];
		visit=new boolean[N+1];
		perm(0);

	}
	
	static void perm(int cnt) {
		if(cnt==C) {
			for(int i=0; i<C; i++) {
				System.out.print(num[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i=1; i<=N; i++) {
			if(visit[i]==false) {
				num[cnt]=i;
				visit[i]=true;
				perm(cnt+1);
				visit[i]=false;
			}
		
		}
		
	}

}

 

 

 

N과 M (2)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.

 

해결방안

• 1에서 고른 수열은 오름차순이어야 한다는 조건이 추가되었다.
  • ->조합코드를 짜서 start값으로 i+1을 넘겨주면, 오름차순으로 코드를 작성할 수 있다.

import java.util.Scanner;

public class Main {

	static int N,C;
	static int num[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input=new Scanner(System.in);
		N=input.nextInt();
		C=input.nextInt();
		num=new int[C];
		comb(0,1);

	}
	
	static void comb(int cnt,int start) {
		if(cnt==C) {
			for(int i=0; i<C; i++) {
				System.out.print(num[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i=start; i<=N; i++) {
				num[cnt]=i;
				comb(cnt+1,i+1);
		
		}
		
	}

}

 

 

 

N과 M (3)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.

 

해결방안

• 같은 수를 여러 번 골라도 된다는 조건이 추가되었다.
  • ->순열코드에서 visit를 빼주면 중복된 값이 나온다.
  • 그냥 출력하면 시간초과가 나서 StringBuilder를 통해 출력해주어야한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

	static int N,C;
	static int num[];
	static boolean visit[];
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		num=new int[C];
		visit=new boolean[N+1];
		sb= new StringBuilder();
		perm(0);
		System.out.println(sb);


	}
	
	static void perm(int cnt) {
		if(cnt==C) {
			for(int i=0; i<C; i++) {
				sb.append(num[i]+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i=1; i<=N; i++) {
				num[cnt]=i;
				perm(cnt+1);
			}
		
		}
		
	}

 

 

 

N과 M (4)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

해결방안

• 고른 수열은 비내림차순이어야 한다는 조건이 추가되었다.
  
  • ->조합코드를 짜서 start값으로 i을 넘겨주면, 중복된 값이 나온다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

	static int N,C;
	static int num[];
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		num=new int[C];
		sb = new StringBuilder();
		comb(0,1);
		System.out.println(sb);

	}
	
	static void comb(int cnt,int start) {
		if(cnt==C) {
			for(int i=0; i<C; i++) {
				sb.append(num[i]+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i=start; i<=N; i++) {
				num[cnt]=i;
				comb(cnt+1,i);
		
		}
		
	}

}

 

N과 M (5)

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

• 수를 입력받아서 작성해야한다는 조건이 추가되었다.
  
  • ->순열코드를 짜서 입력받은 값을 넣어주고, Arrays.sort를 사용해서 정렬해준다.

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

public class Main {

	static int N,C;
	static int num[];
	static int array[];
	static boolean visit[];
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		
		sb = new StringBuilder();
		
		array=new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			array[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(array);
		num=new int[C];
		visit=new boolean[N+1];
		perm(0);
		System.out.println(sb);

	}
	
	static void perm(int cnt) {
		if(cnt==C) {
			for(int i=0; i<C; i++) {
				sb.append(num[i]+" ");
			}
			sb.append("\n");
			return;
		}
		for(int i=0; i<N; i++) {
			if(visit[i]==false) {
				num[cnt]=array[i];
				visit[i]=true;
				perm(cnt+1);
				visit[i]=false;
			}
		
		}
		
	}

}

 

 

 

N과 M (6)

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

• 수를 입력받아서 작성해야하고, 오름차순이여야 한다는 조건이 추가되었다.
  
  • ->조합코드를 짜서 입력받은 값을 넣어주고, Arrays.sort를 사용해서 정렬해준다.

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

public class Main {

	static int N,C;
	static int num[];
	static int array[];
	static boolean visit[];
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		
		sb = new StringBuilder();
		
		array=new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			array[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(array);
		num=new int[C];
		comb(0,0);
		System.out.println(sb);

	}
	
	private static void comb(int cnt, int start) {
		if (cnt == C) {
			for(int i=0; i<C; i++) {
				System.out.print(num[i]+" ");
			}
			return;
		}
		for (int i = start; i < N; i++) {
			num[cnt] = array[i];
			comb(cnt + 1, i + 1);
		}
	}
	
	
}