N과 M

문제 

• 15649번 N과 M (1)
• https://www.acmicpc.net/problem/15649

 

풀이 코드

public class Main {
	public static int []arr;
	public static boolean [] visited;
	public static StringBuilder sb = new StringBuilder();
	public static int n;
	public static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        visited = new boolean[n+1];
        dfs(0);
        System.out.println(sb);
    }
    public static void dfs(int dep) {
    	if(dep == m) {
    		for(int i=0;i<arr.length;i++) {
    			sb.append(arr[i]+" ");
    		}
    		sb.append("\n");
    		return;
    	}
    	for(int i=1;i<=n;i++) {
    		if(!visited[i]) {
    			arr[dep] = i;
    			visited[i] = true;
        		dfs(dep+1);
        		visited[i] = false;
    		}
    	}
    	
    }
}

 

---

문제 

• 15650번 N과 M (2)
• https://www.acmicpc.net/problem/15650

풀이 코드

 

public class Main {
	public static int []arr;
	public static boolean [] visited;
	public static StringBuilder sb = new StringBuilder();
	public static int n;
	public static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        visited = new boolean[n+1];
        dfs(0,1);
        System.out.println(sb);
    }
    public static void dfs(int dep, int start) {
    	if(dep==m) {
    		for(int a : arr) {
    			sb.append(a+" ");
    		}
    		sb.append("\n");
    		return;
    	}
    	for(int i=start;i<=n;i++) {
    		if(!visited[i]) {
    			visited[i] = true;
    			arr[dep] = i;
    			dfs(dep+1,i);
    			visited[i] = false;
    		}
    	}
    }
}

---

 

문제 

• 15651번 N과 M (3)
• https://www.acmicpc.net/problem/15651

풀이 코드

public class Main {
	public static int []arr;
	public static StringBuilder sb = new StringBuilder();
	public static int n;
	public static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        dfs(0);
        System.out.println(sb);
    }
    public static void dfs(int dep) {
    	if(dep==m) {
    		for(int a : arr) {
    			sb.append(a+" ");
    		}
    		sb.append("\n");
    		return;
    	}
    	for(int i=1;i<=n;i++) {
    			arr[dep] = i;
    			dfs(dep+1);

    	}
    }
}

---

 

문제 

• 15652번 N과 M (4)
• https://www.acmicpc.net/problem/15652

풀이 코드

 

public class Main {
	public static int []arr;
	public static StringBuilder sb = new StringBuilder();
	public static int n;
	public static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];
        dfs(0,1);
        System.out.println(sb);
    }
    public static void dfs(int dep, int start) {
    	if(dep==m) {
    		for(int a : arr) {
    			sb.append(a+" ");
    		}
    		sb.append("\n");
    		return;
    	}
    	for(int i=start;i<=n;i++) {
    			arr[dep] = i;
    			dfs(dep+1,i);
    	}
    }
}

 

백트래킹 유형의 N과 M 4문제를 풀어봤다! 백트래킹의 기초는 연습했고 내일부턴 백트래킹 심화문제들을 풀어보려고 한다!