[백준 15664, Java] N과 M (10)

문제

www.acmicpc.net/problem/15664

15664번: N과 M (10)

 

풀이

 N과 M (9)를 확실히 이해했다면 (10), (11) (12)도 비슷한 방향으로 풀 수 있다. N과 M (9)에 대한 풀이는 여기 를 클릭

 

문제의 핵심은, 0~ N-1까지의 숫자 중에서 index에 대한 조건, 값에 대한 조건 체크를 하는 것이다. index에 대한 조건 체크만 있다면 이 문제는 N과 M(4) 와 같은 문제다. 

 

 2 3 7 7 9 에서 비내림차순으로 숫자를 뽑을 때 인덱스를 기준으로 3개를 뽑으면, 0 1 2 / 0 1 3 / 0 1 4/ 0 2 3 ... 이 순서로 뽑게된다. 그런데 인덱스 0 1 2, 0 1 3에 해당 하는 숫자가 모두 2 3 7 이므로 0 1 3은 뽑으면 안됀다. 마찬가지로 0 2 4 를 뽑고 난 뒤 0 3 4를 뽑아도 중복이 된다. 다시말해 같은 자리에 이전에 왔던 숫자가  오면 안된다. 

 

 

코드

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

public class Main {
    public static int N;
    public static int M;
    public static int[] candidates;
    public static int[] numArray;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        candidates = new int[N];
        numArray = new int[M];

        st = new StringTokenizer(br.readLine()," ");
        for(int index = 0; index<N; index++){
            candidates[index] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(candidates);

        pickNums(0, 0, bw);
        bw.flush();

        br.close();
        bw.close();
    }

    public static void pickNums(int index ,int startIndex, BufferedWriter bw) throws Exception{
        if(index>=M){
            for(int num : numArray){
                bw.write(String.valueOf(num)+" ");
            }
            bw.write("\n");
        }
        else{
            int beforeNum = -1;
            for(int i = startIndex ; i<N ; i++){
                if(beforeNum!= candidates[i]){
                    numArray[index] = candidates[i];
                    beforeNum = candidates[i];

                    pickNums(index+1, i+1, bw);
                }
            }
        }
    }
}

 

 

  

 

코드