[백준/JAVA] 15651번: N과 M (3)

🔺 문제

15651번: N과 M (3)

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] A;
    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());
        M = Integer.parseInt(st.nextToken());
        
        A = new int[M];
        
        dfs(0);
        System.out.println(sb);
    }
    
    private static void dfs(int depth) {
        if(depth == M) {
            for(int val : A) {
                sb.append(val + " ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = 1 ; i <= N ; i++) {
            A[depth] = i;
            dfs(depth + 1);
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹 (DFS) : 중복 가능
- 같은 수를 여러번 골라도 된다. 즉, 중복을 고려하지 않아도 되므로 방문 여부를 판단할 필요가 없다.

 

오...  dfs 메소드를 private으로 선언하니 메모리랑 시간이 조금 더 줄어들었다

---

💬 느낀 점

엥.. 솔직히 N과 M (1) (2)보다 얘가 더 쉬웠다,,,

(사실 이래놓고 조금 헤맴)

 

 

1회독	2회독	3회독	4회독	5회독
V	8.29

 

 

(+ 2회독 : 8. 29)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] A, result;
    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());
        M = Integer.parseInt(st.nextToken());
        
        A = new int[N];
        for(int i = 0 ; i < N ; i++) {
            A[i] = i + 1;
        }
        result = new int[M];
        
        back(0);
        System.out.println(sb);
    }
    
    private static void back(int depth) {
        if(depth == M) {
            for(int i : result) sb.append(i).append(" ");
            sb.append("\n");
            return;
        }
        
        for(int i = 0 ; i < N ; i++) {
            result[depth] = A[i];
            back(depth + 1);
        }
    }
}

어랏.. 메모리 사용량을 2배 이상 줄이다...