[백준알고리즘] 브루트포스 - 15619번 N과 M(1) 문제

n과 m이 최대 8인데에 비해 배열 크기를 작게 잡아놨어서 런타임 에러가 생겼었다.

간단히 코드 설명을 하자면

첫번째 자리부터 1로 시작하여, 1을 사용했으니 isUsed의 1번 인덱스에 사용했다고 표시하기 위해 true로 하고

일단 한자리 차지했으니 count를 증가시키고

그 다음 자리에 들어갈 수를 알아보기 위해 printSeries 함수로 재귀하여 사용하지 않은 다른 수를 할당, 체크하고 또 넘어가고

M번만큼 채워졌다면(count==M이 되었다면)출력하고 이전 위치로 돌아간다

출력하고 왔으면 방금 사용한 M-1번째의 수는 다시 false로 되돌려놓는다. count도 하나 감소시키고

그리고 다음 i번값부터 다시 체크...반복...

재귀함수가 아직 익숙치 않아 머릿속으로 그리는게 바로바로 쉽게 되진 않았다.

 

풀이코드

package baekjoonWeek3;

import java.io.*;
import java.util.StringTokenizer;

public class NandM_1 {  //백준 15649번 N과 M 문제
    static int[] nums;
    static boolean[] isUsed;
    static int count = 0;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   //1~N까지의 자연수
        int M = Integer.parseInt(st.nextToken());   //중복없이 M개 고르기
        nums = new int[7];  //N은 최대 8
        isUsed = new boolean[8];    //1칸부터 사용하니까 8은 되어야함!!
        printSeries(N,M,count);
        bw.flush();
        bw.close();
    }
    static void printSeries(int N, int M, int count) throws IOException { 
        for (int i = 1; i <= N; i++) {
            if (count == M) {   //M만큼 다 채웠으면 출력한다
                for (int j = 0; j < M; j++) {
                    bw.write(Integer.toString(nums[j]) + " ");
                }
                bw.newLine();
//                isUsed[i] = false;
                return;
            } else if (!isUsed[i]) {   //사용안한 숫자라면
                nums[count] = i;  //count번에 i 할당
                isUsed[i] = true;   //사용했다 찜함
                count++;
                printSeries(N,M,count);
                isUsed[i] = false;
                count--;
            }

        }
    }
}