[Baekjoon] 15649, 15650, 15651, 15652 N과 M

Silver III

문제 출처:
https://www.acmicpc.net/problem/15649
https://www.acmicpc.net/problem/15650
https://www.acmicpc.net/problem/15651
https://www.acmicpc.net/problem/15652

 

 

---

< N과 M(1) >

문제 

 

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

 

 

입력

 

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력 

 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며,
각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

문제 풀이

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

public class Main {
	static int [] arr;
	static int [] visited;
	
	public static void search(int n, int m, int idx) {
		if(idx==m) {
			for(int i=0; i<m; i++) {
				System.out.print(arr[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i=0; i<n; i++) {
			if(visited[i]==0) {
				visited[i]=1;
				arr[idx]=i+1;
				search(n,m,idx+1);
				visited[i]=0;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		
		arr=new int[m];
		visited=new int[n];
		
		search(n,m,0);

	}
}

 

• main
  : n, m 입력
  : 함수 호출
• search (총 개수, 구하려는 개수, 현재 구한 개수)
  : 구하려는 개수와 현재 구한 개수가 같다면 수열 출력
  : 총개수만큼 반복하여 아직 사용하지 않은 값이라면 그 값을 사용해주고 search 함수를 호출하여 다음 값을 구해줌
  -> 값을 구했다면 다음 수열을 구할 때 그 값을 사용할 수 있도록 visited를 원래대로 돌려줌
  
  

---

< N과 M(2) >

문제 

 

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

 

 

입력

 

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력 

 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며,
각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

문제 풀이

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

public class Main {
	static int[] arr;

	public static void search(int n, int m, int idx, int start) {
		if (idx == m) {
			for (int i = 0; i < m; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
		for (int i = start; i < n; i++) {

			arr[idx] = i + 1;
			search(n, m, idx + 1, i + 1);

		}
	}

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		arr = new int[m];

		int start = 0;
		search(n, m, 0, start);

	}
}

 

• '고른 수열은 오름차순'이어야 하므로 1 2와 2 1은 같다.
  이 부분을 고려하기 위하여 search 함수에서 search함수를 호출할 때 호출한 위치인 i를 넘김으로써 그 전 값은 뽑지 못하게 해 준다. 

---

< N과 M(3) >

문제 

 

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

 

 

입력

 

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

 

출력 

 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며,
각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int[] arr;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	// bufferedWriter 사용해서 시간초과 해결

	public static void search(int n, int m, int idx) throws IOException {
		if (idx == m) {
			for (int i = 0; i < m; i++) {
				bw.write(arr[i] + " ");
			}
			bw.write("\n");
			return;
		}
		for (int i = 0; i < n; i++) {

			arr[idx] = i + 1;
			search(n, m, idx + 1);

		}
	}

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		arr = new int[m];

		search(n, m, 0);

		bw.flush();

	}
}

 

• 같은 수를 여러 번 고르기 위하여 첫 번째 문제에서 visited를 없앴다.

❓ 시간 초과 발생 이유는?

출력문을 작성하는데서 시간 초과가 발생한 것이었다. BufferedWriter를 사용함으로써 시간 초과를 해결할 수 있었다.

 

---

< N과 M(4) >

문제 

 

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

 

 

입력

 

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력 

 

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며,
각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int[] arr;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void search(int n, int m, int idx, int start) throws IOException {
		if (idx == m) {
			for (int i = 0; i < m; i++) {
				bw.write(arr[i] + " ");
			}
			bw.write("\n");
			return;
		}
		for (int i = start; i < n; i++) {

			arr[idx] = i + 1;
			search(n, m, idx + 1, i);

		}
	}

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		arr = new int[m];
		
		int start=0;
		search(n, m, 0, start);

		bw.flush();

	}
}

 

• 바로 위 문제에서 비 내림차순 조건을 추가하였다. search 함수에서 시작하는 위치를 추가함으로써 해결할 수 있었다.

 

---

생각🤔

 

N과 M 문제를 해결하며 백트래킹에 대하여 조금 알게 된 것 같다.

그래도 어렵다!

 

- N과 M(1)

 

- N과 M(2)

 

- N과 M(3)

 

-N과 M(4)

---