백준 14641 N과 M(3) [JAVA]

문제 해석

• 문제는 N과 M(2)에선 중복을 제거했더라면, N과 M(3)에서는 수열의 숫자들이 중복이 허용된 상태에서 NXN개의 경우의 수가 나오면 되는 문제이다.
• N이 4고 M이 2라고 가정했을 때, 기존에는 1 1가 안되었다면 이 문제는 1 1, 2 2, 3 3, 4 4를 모두 허용한다. 그렇기 때문에 NXN개의 경우의 수가 나올 수 밖에 없다. (N과 M은 입력 값이고, N과 M(1), N과 M(2)에서의 N과 M의 의미는 같다.)

코드

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

public class Main {

    static int N; // N
    static int M; // M
    static int[] list; //해당 순열을 저장하는 배열
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); //N
        M = Integer.parseInt(st.nextToken()); //M

        list = new int[M]; //M개의 숫자의 순열 저장하는 배열 초기화

        backTracking(0); // 배열에 저장할 열 인덱스만 파라미터로 넘긴다.
        br.close();
        System.out.println(sb);
    }

    //start부분을 파라미터에 추가한 이유
    // start를 추가하여 시작점을 바꿨다
    static void backTracking(int row) {
        if (row == M) { //순열의 크기가 M일 경우(M개의 숫자 순열을 고르는 거기때문에 이때 종료
            for(int value : list){
                sb.append(value + " "); //순열 차례대로 배열에서 꺼내서 StringBuilder에 추가
            }
            sb.append("\n");
            return;
        }

        //시작점을 설정하지 않고 1부터 쭉 나올 수 있도록 설정한다.
        for (int i = 1; i <= N; i++) {
            list[row] = i; // 해당 수열을 추가
            backTracking(row+1); //자식노드 방문
        }
    }
}

결과

느낀 점

• N과 M(1), N과 M(2) 문제를 풀었다면, 이 문제는 1분안에는 풀 수 있는 문제이다. (N과 M(2) 코드에서 살짝만 바꾸면 풀리는 문제)
• 빠르게 풀려서 '틀렸습니다' 나오는 거 아닌가 싶었는데 다행히 '맞았습니다!!'가 나왔다.