[백준] 15650번: N과 M (2)
📝 문제
백트레킹으로 사용한 숫자인지 표시를 해야하는데 문제를 풀다보니 굳이 해야하나? 하는 생각이 들었다
어차피 오름차순의 순열이고 이전의 숫자보다 큰 숫자들 중에서 다음 수를 선택하는거니까
필요 없다는 생각이 들었다.
그래서 그냥 재귀 알고리즘으로 코드를 짰다.
📌 코드
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ15650 {
static int n,m;
static StringBuilder sb = new StringBuilder();
static void dfs(int cur, int cnt, String str){
if(cnt == m) {
sb.append(str).append("\n");
return;
}
if(cur > n) return;
for(int i = cur+1; i <= n; i++){
String curStr = str + " " + i;
dfs(i, cnt+1, curStr);
}
}
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());
for(int i = 1; i <= n+1-m; i++){
dfs(i, 1, String.valueOf(i));
}
System.out.println(sb.toString());
}
}
Author And Source
이 문제에 관하여([백준] 15650번: N과 M (2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@paulus0617/15650
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ15650 {
static int n,m;
static StringBuilder sb = new StringBuilder();
static void dfs(int cur, int cnt, String str){
if(cnt == m) {
sb.append(str).append("\n");
return;
}
if(cur > n) return;
for(int i = cur+1; i <= n; i++){
String curStr = str + " " + i;
dfs(i, cnt+1, curStr);
}
}
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());
for(int i = 1; i <= n+1-m; i++){
dfs(i, 1, String.valueOf(i));
}
System.out.println(sb.toString());
}
}
Author And Source
이 문제에 관하여([백준] 15650번: N과 M (2)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@paulus0617/15650저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)