[백준15652] N과 M (4) / Java

TITLE

문제주소 :www.acmicpc.net/problem/15652

 

---

<문제 설명>

문제

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

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

입력

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

출력

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

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

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

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

예제 입력 3

3 3

예제 출력 3

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

<풀이법>

▒ 한줄 개념: 조건문 추가 ▒ 

2021/01/06 - [Baekjoon] - [백준15651] N과 M (3) / Java

2021/01/05 - [Baekjoon] - [백준15650] N과 M (2) / Java

2021/01/05 - [Baekjoon] - [백준15649] N과 M (1) / Java

 

전의 N과 M 문제와 거의 동일하지만, 조건문을 추가해주어야 합니다.

조건문 추가 부분에서 count값의 수정이 필요하여, 시작 Argument를 수정해주었습니다.

재귀함수 내 구현은 다음과 같습니다.

• count값이 array.length와 같으면 버퍼에 쓰기
• count가 0이면 시작하는 것이므로 조건문 없이 array에 넣기
• count가 1이상이면 한 칸 앞의 값과 비교 후(조건문) 통과시 array에 넣기

 

<코드(Java)>

package Baekjoon;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class N_and_M_4_15652 {
    static BufferedWriter buf = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] array = new int[M];

        search(0, array, N);
        try {
            buf.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static void search(int count, int[] array, int N) {
        try {
            if (count == array.length) {
                for(int a :array){
                    buf.append(a+" ");
                }
                buf.write("\n");
            } else if(count == 0){
                for (int i = 0; i < N; i++) {
                    array[0] = i + 1;
                    search(1, array, N);
                }
            } else {
                for (int i = 0; i < N; i++) {
                    if (i + 1 >= array[count-1]){
                        array[count] = i + 1;
                        search(count + 1, array, N);
                    }
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest