[BruteForce] 백준 15652: N과 M(4)

15652번: N과 M (4) (acmicpc.net)

15652번: N과 M (4)

정답률 무려 79퍼.

 

바빠서 리뷰는 나중으로 미뤄뒀지만 어제 N과 M 1~3을 무난히 통과한 나는 자신감 있게 덤볐지만, 모종의 이유로 잠시 고생을 했다.

 

기본적으로 N과 M 1~3과 같으나, 정답을 추가할 때 "비내림차순" 조건에 들어맞는지 확인하는 구문을 넣어 주면 된다.

 

    static void findAnswer(int[] arr,int depth,int r,int[] answer) throws IOException {
        if(depth==r){
            //정답 출력
            for(int i=0;i<answer.length;i++){
                bw.write(answer[i]+" ");
            }
            bw.newLine();
            return;
        }

        for(int i=0;i<N;i++){
            if(depth==0){
                //맨 첫 단계에서는 그냥 넣으면 됨.
                answer[depth] = arr[i];
                findAnswer(arr,depth+1,r,answer);
            }else{
                //비내림차순인지 확인
                if(answer[depth-1]<=arr[i]){
                    answer[depth] = arr[i];
                    findAnswer(arr,depth+1,r,answer);
                }else{
                    break;
                }
            }
        }
    }

즉 depth가 0인 경우에는 어차피 비교 대상이 없으니 정답 배열(answer)에 무조건 수를 넣어 주고, 그 다음부터 depth==r 탈출조건을 만족할 때까지는 정답 배열에 이미 들어와 있는 마지막 수와 비교하면서 넣을지, 넘어갈지를 결정해주면 된다. 

 

그런데 이 코드를 돌리면 가령 4,2의 input을 받은 경우, (1,1),(1,2),(1,3),(1,4) 까지만 출력하고 프로그램이 종료되어 버린다.

 

그 이유는 바로 쓸데없는 break문을 잘못 넣었기 때문이다.

if(answer[depth-1]<=arr[i]){
                    answer[depth] = arr[i];
                    findAnswer(arr,depth+1,r,answer);
                }else{
                    break;
                }

여기 else문에서 break구문을 만나면 저 if문을 빠져나가는 게 아니라 상위의 for문 자체를 빠져나가 버린다. 그래서 2부터 시작되는 수열들을 만들지 못하고 끝나 버린 것이다. 

 

이런 문제는 사실 그냥 마우스만 대 봐도 바로바로 문제를 알 수 있는 건데, 당연히 어딘가에 내가 모르는 중대하고 심오한 오류가 있을 거라고 생각하며 다 뜯어 보느라 시간이 좀 걸렸다.

 

올바르게 수정한 코드는 아래와 같다. 올바르게 수정한 함수를 먼저 올리고, 전체 코드 올리고 마친다.

 

static void findAnswer(int[] arr,int depth,int r,int[] answer) throws IOException {
        if(depth==r){
            //정답 출력
            for(int i=0;i<answer.length;i++){
                bw.write(answer[i]+" ");
            }
            bw.newLine();
            return;
        }

        for(int i=0;i<N;i++){
            if(depth==0){
                //맨 첫 단계에서는 그냥 넣으면 됨.
                answer[depth] = arr[i];
                findAnswer(arr,depth+1,r,answer);
            }else{
                //비내림차순인지 확인
                if(answer[depth-1]<=arr[i]){
                    answer[depth] = arr[i];
                    findAnswer(arr,depth+1,r,answer);
                }else{
                    break;
                }
            }
        }
    }

<전체 코드>

import java.io.*;

public class BOJ_15652_re {
    static int N,M;
    static int[] arr;
    static int[] answer;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NM = br.readLine().split(" ");
        N = Integer.parseInt(NM[0]);
        M = Integer.parseInt(NM[1]);
        arr = new int[N];

        for(int i=0;i<N;i++){
            arr[i] = i+1;
        }
        answer = new int[M];

        findAnswer(arr,0,M,answer);
        bw.flush();
    }

    static void findAnswer(int[] arr,int depth,int r,int[] answer) throws IOException {
        if(depth==r){
            //정답 출력
            for(int i=0;i<answer.length;i++){
                bw.write(answer[i]+" ");
            }
            bw.newLine();
            return;
        }

        for(int i=0;i<N;i++){
            if(depth==0){
                //맨 첫 단계에서는 그냥 넣으면 됨.
                answer[depth] = arr[i];
                findAnswer(arr,depth+1,r,answer);
            }else{
                //비내림차순인지 확인
                if(answer[depth-1]<=arr[i]){
                    answer[depth] = arr[i];
                    findAnswer(arr,depth+1,r,answer);
                }else{
                    break;
                }
            }
        }
    }
}