백준 15657번: N과 M(8) with Java

N과 M (8)

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

27019

21964

18799

81.300%

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1
4 5 2

예제 출력 1 복사

2
4
5

예제 입력 2 복사

4 2
9 8 7 1

예제 출력 2 복사

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

예제 입력 3 복사

4 4
1231 1232 1233 1234

예제 출력 3 복사

1231 1231 1231 1231
1231 1231 1231 1232
1231 1231 1231 1233
1231 1231 1231 1234
1231 1231 1232 1232
1231 1231 1232 1233
1231 1231 1232 1234
1231 1231 1233 1233
1231 1231 1233 1234
1231 1231 1234 1234
1231 1232 1232 1232
1231 1232 1232 1233
1231 1232 1232 1234
1231 1232 1233 1233
1231 1232 1233 1234
1231 1232 1234 1234
1231 1233 1233 1233
1231 1233 1233 1234
1231 1233 1234 1234
1231 1234 1234 1234
1232 1232 1232 1232
1232 1232 1232 1233
1232 1232 1232 1234
1232 1232 1233 1233
1232 1232 1233 1234
1232 1232 1234 1234
1232 1233 1233 1233
1232 1233 1233 1234
1232 1233 1234 1234
1232 1234 1234 1234
1233 1233 1233 1233
1233 1233 1233 1234
1233 1233 1234 1234
1233 1234 1234 1234
1234 1234 1234 1234

 

 

 

---

 

이게 또 무슨 말이야~

꼴랑 2개를 풀었지만 경험상 일단 입출력을 보는 게 더 빠르더라

 

1. 첫쨰 줄 N과 M (1 <= M <= N <= 8)

2. N개의 수.... 

 

 

모르겠다.

빠르더라 취소

 

 

n개의 자연수 중 m개를 고른 수열 -> 오 조합?

같은 수를 여러 번 골라도 된다 -> 오 중복 조합?

비내림차순.....?????? 비내림차순이뭐임 

구글링 결과 비내림차순은 점점 증가하는 수열인데 인접한 수들이 같을 수도 있다는 거...!!!!ㅎ

 

예제 출력을 보니까 좀 알 것 같기도 하고 아직은 알쏭달쏭하다. 

중복 순열인지 중복 조합인지 헷갈려서 차이를 검색해봤는데 [1, 2] [2, 1] 이 있을 때 순열은 이걸 다른 걸로 보고 조합은 같은 걸로 본단다. 순열은 순서 있음...!!! 

근데 얘는 수열이라 했고.. 중복되는 수열 여러 번 출력X 결정적으로 출력 결과에 1 7은 있어도 7 1은 없었음 중복 조합이다!!!

 

중복 조합은 문해기 때 C로 pick 함수 만들어서 재귀로 썼던 기억만 나는데 이걸 자바로 어떻게 짜지 ㅎ

 

하다 보니까 일단 입력 받은 숫자를 정렬 먼저해야 할 듯...

정렬 알고리즘 짜려다가 혹시 하고 검색했는데 Arrays.sort(배열이름); 으로 정렬 완료... 행복해

 

첫 번째 코드...

import java.util.Arrays;
import java.util.Scanner;
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	
		int n = sc.nextInt();	// 전체 숫자 개수
		int m = sc.nextInt();	// 뽑을 숫자 개수
		
		int[] nums = new int[n];	// 입력 받는 int 배열
		for (int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}
		Arrays.sort(nums);
		
		int[] picked = new int[m];	// 결과 담을 배열
		pick(n, m, m, nums, picked);	
		
		sc.close();
	}
	
	// n개의 숫자 중에서 m개를 뽑아 출력
	static void pick(int n, int m, int toPick, int[] nums, int[] picked) {
		int lastIndex = m - toPick - 1;
		int smallest;
		if (m == toPick)
			smallest = 0;
		else
			smallest = picked[lastIndex] + 1;
		
		if (toPick == 0) {
			for (int num: picked) {
				System.out.print(nums[num] + " ");
			}
			System.out.println();
			
			return;
		}
		else {
			for (int i = smallest; i < n; i++) {
				picked[lastIndex + 1] = i;
				pick(n, m, toPick - 1, nums, picked);
			}
		}
	}
}

 

 

양심 고백... 솔직히 말하면 자꾸 헷갈려서 예전에 수업 들으면서 풀었던 코드를 갖고 와서 좀 변형시켰다... 

근데 안 돌아감ㅎ

실수로 중복 조합이 아니라 그냥 조합을 갖고 온 듯 함

 

 

비내림차순이기 때문에 smallest에 1을 더해줄 필요가 없다.

smallest = picked[lastIndex]; 이거로 수정하고 돌렸더니

import java.util.Arrays;
import java.util.Scanner;
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	
		int n = sc.nextInt();	// 전체 숫자 개수
		int m = sc.nextInt();	// 뽑을 숫자 개수
		
		int[] nums = new int[n];	// 입력 받는 int 배열
		for (int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}
		Arrays.sort(nums);
		
		int[] picked = new int[m];	// 결과 담을 배열
		pick(n, m, m, nums, picked);	
		
		sc.close();
	}
	
	// n개의 숫자 중에서 m개를 뽑아 출력
	static void pick(int n, int m, int toPick, int[] nums, int[] picked) {
		int lastIndex = m - toPick - 1;	// 뽑을 전체 개수 - 뽑아야 할 개수 - 1 (지금까지 뽑은 인덱스 번호)
		int smallest;
		if (m == toPick)
			smallest = 0;	// 처음 뽑는 거면 0
		else	
			smallest = picked[lastIndex];	// 비내림차순, 중복 허용이므로 제일 마지막에 뽑은 게 smallest가 됨
		
		// 더이상 뽑을 거 없으면 출력
		if (toPick == 0) {
			for (int num: picked) {
				System.out.print(nums[num] + " ");
			}
			System.out.println();
			
			return;
		}
		else {
			for (int i = smallest; i < n; i++) {
				picked[lastIndex + 1] = i;
				pick(n, m, toPick - 1, nums, picked);
			}
		}	// 아니라면 smallest를 i로 잡고 반복문 돌림 맨 마지막에 i 넣어주고 재귀
	}
}

 

 

근데 이제 슬슬 저 용량과 속도가 거슬리기 시작한다... 주석도 용량으로 쳐지나??

암튼 시간이 너무 지나치게 많이 걸린다는 생각이....^^......

풀고 나서 검색해보니까 백트래킹 DFS 이야기가 많이 보였다. 하긴 생각해보니 깊이가 맞네...??? 자료구조 시간에 배운 것 같은데.... 지금 풀었다고 좋아할 때가 아니었다. 나갔다와서 다시 속도 줄이는 걸로 해보는 걸로~