1182: 부분수열의 합

부분수열알고리즘을 어떻게만들지?
일단은 뭐든간 정렬뒤에 부분수열을 만들것같긴한데..

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;

public class Main{
    static int n;
    static long sum;
    static int num[];
    static int count;
    public static void dfs(int depth, int curSum){
        //depth = 내가 처리해놓은, 방문한메서드의개수 즉, 처리한 원소의개수
        //난 n개의 모든 원소에 대해 처리를 완료한 경우만 return한다
        if(depth==n){
            if(sum == curSum) count++;
            return;
        }
        //depth가 n보다 작은경우에만 이곳으로 올수가있다. n보다 같거나 크게되면 함수종료돼버림
        dfs(depth+1, curSum + num[depth]);
        dfs(depth+1, curSum);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        sum = Integer.parseInt(input[1]);
        String arr[] = br.readLine().split(" ");
        num = new int[n];
        for(int i=0;i<n;i++){
            num[i] = Integer.parseInt(arr[i]);
        }
        //s = 0인경우, 모두선택안한 공집합인 경우도 ++ 됨.
        //나머지의 경우 모두 선택을 안하더라도 공집합이 되더라도 합이 0이아니니까 더 추가되는경우없음
        dfs(0,0);
        //sum=0, count=0인경우도 있을줄알았는데 모든 집합에서나 공집합은 있으니 그런 경우는 없을것이다
        //아래의 경우의수만 고려해주면된다
        if(sum==0) System.out.println(count-1);
        else System.out.println(count);

    }


}

15650: N과M

풀이

• 매번 숫자를 바라본다. 이 숫자를 택할수도있고 아닐수도있다.
• 숫자를 택하든 아니든 이 숫자의 개수가 m개가 될경우에는 출력을 해주어야한다
• 내가 바라보는 숫자를 넣든 안넣든 나는 1부터 n까지의 모든 숫자를 바라보고, 출력할지를 결정해야한다
• 내가 1부터n까지의 모든 숫자를 바라봤고, 그러니까 각 상황에서 이 숫자를 출력할지 말지를 고민했고, 그 고민에 의해 출력문으로 쓰일 str에 추가를 하거나 하지 않았다. 그리고 이 숫자의 개수가 m개가 됐다. 이경우에는 출력을 해준다.
• 초과가되는 경우에 대해서는 return으로 더이상 stack에 메서드가 쌓이는것을 없애준다

코드

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;

public class Main{
    static int n;
    static int m;
    // 답을 return하는 메서드를 만든다
    // 모든경우의 수를 따져야하기에 dfs로 풀려고하였다.
    public static void dfs(int idx, int depth, String str){
        //처음엔 아래조건을 안넣었다. 그얘긴 출력할때만 return한다는얘기다.
        //출력조건에 해당하지 않더라도 return하는 조건이 필요하다
        if(depth > m || idx > n+1) return;
        //m번째까지 출력을했거나 모든 숫자를 다돈경우에는 출력을한다
        //idx는 내가 보고있는 숫자를 의미한다 내가 보고있는 숫자가 n+1이라는것은 1~n까지의 숫자를 모두봤다는 의미다
        //depth는 내가 출력문으로 넣은 숫자의 갯수를 의미한다
        if(depth==m&& idx==n+1) {
            System.out.println(str);
            return;
        }
        //str이 아무것도 쓰여져있는 경우에도 아래아래 명령문을 실행하면 출력문이 이상해지기에 추가해줌
        if(str.isEmpty()) dfs(idx+1, depth+1, "" + idx);
        //idx = 내가 바라보는 숫자(건너뛸수도있다), depth=내가출력한숫자의개수
        else dfs(idx+1, depth+1, str + " " + idx);
        //내가 바라보는숫자를 건너뛰는 경우
        dfs(idx+1, depth, str);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        // 1~n까지의 수열중
        n = Integer.parseInt(input[0]);
        // 중복없이 m개를 오름차순으로 선택
        m = Integer.parseInt(input[1]);
        dfs(1,0,"");

    }


}

두번째풀이

//n개의 숫자가 입력되면 그만둬야한다. 이를 판별할 depth라는 변수
    //idx는 앞으로 출력할 숫자를 의미한다
    //str은 넘긴 숫자를 출력할 문자열이다
    public static void NM(int depth, int idx, String str){
        //재귀함수는 기본적으로 종료조건이 필요하다
        if(idx > n) return;
        if(depth==m) {
            System.out.println(str);

            return;
        }
        //오름차순으로만 출력하려면 계속해서 idx를 추가시켜서 넘겨주는 방법이있다
        //빈칸처리를 위해 조건문을 삽입하였다
        if(depth!=0) NM(depth+1, idx+1, str+" "+ (idx+1));
        else NM(depth+1, idx+1, str+""+ (idx+1));
        //처음부터 큰숫자를 하려면 일단 idx를 선택하지 않아야한다
        //str을 그냥넘겨준다는것은 해당 idx를 선택하지않았음을 의미하고
        //depth를 그대로 넘겨줌으로써 idx를 선택하지 않았음을 의미하게 된다
        NM(depth, idx+1, str);


    }

6603: 로또

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;

public class Main{
    static int arr[];
    //str:만들어나가는 출력문, checknum:1~n까지의숫자를 일단 판단. 지금현재판단하는 숫자, printnum:내가출력한 숫자의개수, n:arr배열의길이
    public static void dfs(String str, int checkNum, int printNum, int n){
        //이 문제의 핵심은 일단 요소가 6개가 되면 출력을해야한다는것이다
        //두번째 if문이 첫번째 if문 뒤에와야한다., 왜냐면 저 조건에서 return해주는 이유는 세번쨰 if문에서 배열에 접근할떄 범위밖이라고 error터지기떼문
        if(printNum == 6){
            System.out.println(str);
            return;
        }
        //요소가 6개를 넘어가거나 내가 보는 숫자가 배열개수를 넘어가면 끝내버린다.
        if(checkNum > n || printNum > 6) return;
        //일단 맨처음으로 str이 들어오면 그 숫자는 현재들어온 배열요소와 함께 넘겨버린다
        if(str.isEmpty()) dfs(arr[checkNum]+"", checkNum+1, printNum+1, n);
        //두번쨰부터 str이 들어오면 이전 str에 배열의 그다음 요소를 붙인다. checknum은 항상 + 해야한다. 이메서드하나에서는 항상 하나의 숫자확인이 이루어지니까
        //반면에 printnum은 이루어질수도있고 아닐수도있다
        else dfs(str+" "+ arr[checkNum], checkNum+1, printNum+1, n);
        //이 아래 명령문에서는 str이 아무것도 추가되지않는다. 그렇기때문에 printnum에도 +1이 붙지않는다
        //내알고리즘은 각 숫자에 대해 들어갈것인지 아닌지를 묻고, 그 지점에서 분기하여 재귀호출을하는 방식이다
        dfs(str, checkNum+1, printNum, n);

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input[] = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);

        // 무한호출로 만들어놓고, 0의입력이 들어올떄만 나가도록 설정한다
        while(true){
            arr = new int[n+1];
            //첫번째 넘겨준 값은 개수를 의미한다. 그개수만큼 반복문을 돌아서 배열에 숫자들을 저장한다
            for(int i=1;i<=n;i++){
                arr[i] = Integer.parseInt(input[i]);
            }
            //checknum으로 넘겨주는 숫자의의미: 내가 이숫자부터보겠다의의미. 인자로 1이 들어왔으면 해당메서드에서 arr[1]을 살펴보고 그 값에 따라 분기할예정이라는 의미
            //printnum: 해당메서드에서 다음메서드로 값을 넘겨줄때의 내가 출력한 숫자의 개수
            
            dfs("", 1, 0, n);
            //각 출력문은 개행으로 구분짓는다
            System.out.println();
            String str = br.readLine();
            if(str.equals("0")) {
                int s =2;
                return;
            }
            //input은 띄어쓰기로 구분된다
            input = str.split(" ");
            //다음입력을 받는다
            n = Integer.parseInt(input[0]);
        }
    }
}