백준 15654 : n과 m (5)
처음엔 조합으로 했다가 조합으로는 7 1 같이 순서가 반전된게 나올수 없다고 깨달았다 ..ㅠㅠ 애초에 순열로 풀어야되는걸 깨달았다. 그래서 비트마스크를 이용하여 풀었다
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
static int n,m;
static int cnt=0,tmp2=0;
static int arr[];
static int tmp[];
static int flag;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
tmp=new int[m];
for(int a=0;a<n;a++) {
arr[a]=scan.nextInt();
}
Arrays.sort(arr);
solve(0,0);
System.out.print(sb);
}
public static void solve(int cnt,int used) { //n개의 자연수 중 m개를 고른 수열
if(cnt==m) {
for(int i=0;i<m;i++) {
sb.append(tmp[i]+" ");
}
sb.append("\n");
return;
}
for(int i=0;i<n;i++) {
if((used&1<<i)!=0) {//i번째 원소가 사용됐으면
continue;
}
tmp[cnt]=arr[i]; //사용되지 않았으면 tmp에 저장
solve(cnt+1,used|1<<i);
}
}
}복습
import java.io.*;
import java.util.*;
public class Main {
static int n,m,cnt=0;
static String str;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
static int[] arr,ans;
static boolean[] visited;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
ans=new int[m];
for(int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
Arrays.sort(arr);
visited=new boolean[n];
solve(0);
System.out.print(sb);
}
static void solve(int depth) {
if(depth==m) {
for(int a=0;a<m;a++) {
System.out.print(ans[a]+" ");
}
System.out.println();
return;
}
for(int i=0;i<n;i++) {
if(visited[i]==false) {
visited[i]=true;
ans[depth]=arr[i];
solve(depth+1);
visited[i]=false;
}
}
}
}sb를 이용하면 순서가 오름차순이 되니까 systemout을 사용했다.
백준 15655 : n과 m(6)
아까 위에 문제 풀다가 나온게 이문제 답이였다 ^^..
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
static int n,m;
static int cnt=0,tmp2=0;
static int arr[];
static int tmp[];
static int flag;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
tmp=new int[n];
for(int a=0;a<n;a++) {
arr[a]=scan.nextInt();
}
Arrays.sort(arr);
solve(0,0,false);
System.out.print(sb);
}
public static void solve(int pos,int choice,boolean flag) { //n개의 자연수 중 m개를 고른 수열
if(pos>n) {
return;
}
if(flag==true) {
tmp[pos-1]=1;
}
if(flag==false&&pos!=0) {
tmp[pos-1]=0;
}
if(choice==m) {
for(int i=0;i<n;i++) {
if(tmp[i]==1) {
sb.append(arr[i]+" ");
}
}
sb.append("\n");
return;
}
solve(pos+1,choice+1,true);
solve(pos+1,choice,false);
return;
}
}복습
import java.io.*;
import java.util.*;
public class Main {
static int n,m,cnt=0;
static String str;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
static int[] arr,ans;
static boolean[] visited;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
ans=new int[m];
for(int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
Arrays.sort(arr);
visited=new boolean[n];
solve(0,0);
System.out.print(sb);
}
static void solve(int depth,int start) {
if(depth==m) {
for(int a=0;a<m;a++) {
System.out.print(ans[a]+" ");
}
System.out.println();
return;
}
for(int i=start;i<n;i++) {
if(visited[i]==false) {
visited[i]=true;
ans[depth]=arr[i];
solve(depth+1,i+1);
visited[i]=false;
}
}
}
}앞문제를 조합으로 변경한것
백준 15656 : n과 m(7)
5번문제에서 used를 체크하지않고 그냥 반복하면 되는 문제이다.
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
static int n,m;
static int cnt=0,tmp2=0;
static int arr[];
static int tmp[];
static int flag;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
tmp=new int[m];
for(int a=0;a<n;a++) {
arr[a]=scan.nextInt();
}
Arrays.sort(arr);
solve(0);
System.out.print(sb);
}
public static void solve(int cnt) { //n개의 자연수 중 m개를 고른 수열
if(cnt==m) {
for(int i=0;i<m;i++) {
sb.append(tmp[i]+" ");
}
sb.append("\n");
return;
}
for(int i=0;i<n;i++) {
tmp[cnt]=arr[i]; //사용되지 않았으면 tmp에 저장
solve(cnt+1);
}
}
}복습
import java.io.*;
import java.util.*;
public class Main {
static int n,m,cnt=0;
static String str;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
static int[] arr,ans;
static boolean[] visited;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
ans=new int[m];
for(int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
Arrays.sort(arr);
visited=new boolean[n];
solve(0);
System.out.print(sb);
}
static void solve(int depth) {
if(depth==m) {
for(int a=0;a<m;a++) {
sb.append(ans[a]+" ");
}
sb.append("\n");
return;
}
for(int i=0;i<n;i++) {
ans[depth]=arr[i];
solve(depth+1);
}
}
}
system 쓰면 timeout
백준 15657 : n과 m (8)
이전 문제와 비슷하고 for문 시작하는 부분이 이전 재귀에서 pos부터 시작하면 된다!
import java.util.*;
public class Main {
public static Scanner scan =new Scanner(System.in);
public static StringBuilder sb=new StringBuilder();
static int n,m;
static int cnt=0,tmp2=0;
static int arr[];
static int tmp[];
static int flag;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
tmp=new int[m];
for(int a=0;a<n;a++) {
arr[a]=scan.nextInt();
}
Arrays.sort(arr);
solve(0,0);
System.out.print(sb);
}
public static void solve(int cnt,int pos) { //n개의 자연수 중 m개를 고른 수열
if(cnt==m) {
for(int i=0;i<m;i+=1) {
sb.append(tmp[i]+" ");
}
sb.append("\n");
return;
}
for(int i=pos;i<n;i++) {
tmp[cnt]=arr[i]; //사용되지 않았으면 tmp에 저장
solve(cnt+1,i);
}
}
}복습
import java.io.*;
import java.util.*;
public class Main {
static int n,m,cnt=0;
static String str;
static Scanner scan=new Scanner(System.in);
static StringBuilder sb=new StringBuilder();
static int[] arr,ans;
static boolean[] visited;
public static void main(String[] args) {
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
ans=new int[m];
for(int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
Arrays.sort(arr);
visited=new boolean[n];
solve(0,0);
System.out.print(sb);
}
static void solve(int depth,int start) {
if(depth==m) {
for(int a=0;a<m;a++) {
sb.append(ans[a]+" ");
}
sb.append("\n");
return;
}
for(int i=start;i<n;i++) {
ans[depth]=arr[i];
solve(depth+1,i);
}
}
}
남기고 싶은 개발자입니다 :>