백준 6603번 로또

문제

나의 풀이

import java.util.*;

public class Main {
    static ArrayList<Integer> lotto = new ArrayList<>();
    static void solve(int a[], int index, int count) {
        if(count == 6) {
            for(int num : lotto) {
                System.out.print(num + " "); // 조합 출력
            }
            System.out.println();
            return;
        }
        int n = a.length;
        if(n == index) { // 불가능한 경우
            return;
        }
        
        // 선택하는 경우
        lotto.add(a[index]);
        solve(a, index + 1, count + 1);
        // 선택하지 않는 경우
        lotto.remove(lotto.size() - 1);
        solve(a, index + 1, count);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            int n = sc.nextInt();
            if(n == 0) {
                break;
            }
            int a[] = new int[n];
            for(int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            solve(a, 0, 0); // 재귀 함수 호출
            System.out.println();
        }
    }
}

각각의 수를 고른다와 고르지 않는다로 구분하여 모든 조합을 출력하면 된다.
go 함수를 구현한다. 매개변수인 a는 입력으로 주어진 수, index는 선택할지 말지 결정해야 하는 인덱스, count는 현재까지 포함한 수의 개수를 뜻한다.
정답을 찾는 경우는 count가 6일 때고, 불가능한 경우는 count가 6이 아닌데 index가 a의 크기와 같을 때=더이상 선택할 수 없을 때이다.
다음 경우는 선택하는 경우에는 go(a, index + 1, count + 1), 선택하지 않는 경우는 go(a, index + 1, count)이다.

결과

백준 1182번 부분수열의 합

문제

나의 풀이

import java.util.*;

public class Main {
    public static int go(int a[], int m, int i, int sum) {
        if(i == a.length) {
            if(sum == m) { // 정답을 찾은 경우
                return 1;
            } else {
                return 0;
            }
        }
        return go(a, m, i + 1, sum + a[i]) + go(a, m, i + 1, sum);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int answer = go(a, m, 0, 0);
        if(m == 0) {
            answer -= 1;
        }
        System.out.println(answer);
    }
}

go 함수를 구현하는데 매개변수인 index는 부분 수열에 포함할지 말지 결정해야 하는 인덱스, sum은 현재까지 부분수열의 합을 뜻한다.
정답을 찾는 경우는 index가 n이면서 sum이 s인 경우이고, 불가능한 경우는 index가 n이면서 sum이 s가 아닌 경우다.
다음 경우는 index번째를 부분 수열에 추가하는 경우는 go(index + 1, sum + a[i])이고, index번째를 부분 수열에 추가하지 않는 경우는 go(index + 1, sum)이다.

결과

백준 14225번 부분수열의 합

문제

나의 풀이

import java.util.*;

public class Main {
    static boolean c[] = new boolean[20 * 100000 + 10];
    static int a[] = new int[20];
    static int n;
    static void go(int i, int sum) {
        if(i == n) {
            c[sum] = true;
            return;
        }
        go(i + 1, sum + a[i]);
        go(i + 1, sum);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        go(0, 0);
        for(int i = 1; ; i++) {
            if(c[i] == false) {
                System.out.println(i); // 만들 수 없는 가장 작은 자연수
                break;
            }
        }
    }
}

합을 만들면 c라는 배열에 true를 저장해놓고, 1부터 for문을 돌면서 c가 false인 i값을 찾아 출력시키면 된다.

결과

백준 14888번 연산자 끼워넣기

문제

나의 풀이

import java.util.*;

public class Main {
    static class Pair {
        public int min, max;
        Pair(int min, int max) {
            this.min = min;
            this.max = max;
        }
    }
    static Pair calc(int a[], int index, int cur, int plus, int minus, int mul, int div) {
        int n = a.length;
        if(index == n) {
            return new Pair(cur, cur);
        }
        ArrayList<Pair> res = new ArrayList<>();
        if(plus > 0) {
            res.add(calc(a, index + 1, cur + a[index], plus - 1, minus, mul, div));
        }
        if(minus > 0) {
            res.add(calc(a, index + 1, cur - a[index], plus, minus - 1, mul, div));
        }
        if(mul > 0) {
            res.add(calc(a, index + 1, cur * a[index], plus, minus, mul - 1, div));
        }
        if(div > 0) {
            res.add(calc(a, index + 1, cur / a[index], plus, minus, mul, div - 1));
        }
        Pair answer = res.get(0);
        for(Pair p : res) {
            answer.max = Math.max(answer.max, p.max);
            answer.min = Math.min(answer.min, p.min);
        }
        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int plus = sc.nextInt();
        int minus = sc.nextInt();
        int mul = sc.nextInt();
        int div = sc.nextInt();
        Pair answer = calc(a, 1, a[0], plus, minus, mul, div);
        System.out.println(answer.max);
        System.out.println(answer.min);
    }
}

calc 함수의 매개변수 a는 입력으로 주어진 수열, index는 현재 계산해야 하는 인덱스, cur은 index - 1번째까지 계산한 결과, plus minus mul div는 사용할 수 있는 연산자의 개수를 뜻한다. 리턴값은 최대값과 최소값을 리턴한다.
정답을 찾은 경우는 index가 n인 경우이다.
다음 경우는 4가지가 있는데
+를 사용하는 경우에는 calc(a, index + 1, cur + a[index], plus - 1, minus, mul, div)를 호출하며 결과값을 res에 추가한다.
-를 사용하는 경우에는 calc(a, index + 1, cur - a[index], plus, minus - 1, mul, div)를 호출하며 결과값을 res에 추가한다.
x를 사용하는 경우에는 calc(a, index + 1, cur * a[index], plus, minus, mul - 1, div)를 호출하며 결과값을 res에 추가한다.
/를 사용하는 경우에는 calc(a, index + 1, cur / a[index], plus, minus, mul, div - 1)를 호출하며 결과값을 res에 추가한다.
그런 다음 res에 대하여 for문을 돌면서 가장 큰 값은 answer의 max에 가장 작은 값은 answer의 min에 저장해서 리턴해주면 된다.

결과

인프런 최대 길이 연속수열

문제

나의 풀이

import java.util.HashSet;

public class MCNSS {
    public static int solution(int[] nums) {
        int answer = 0;
        HashSet<Integer> set = new HashSet<>();
        for(int x : nums) {
            set.add(x); // 중복 제거하며 추가
        }
        for(int x : set) {
            if(set.contains(x - 1)) { // 현재 수보다 1 작은 수가 있는 경우
                continue; // 탐색할 필요 없음 (1 작은 수부터 탐색해야 하기 때문)
            }
            int count = 0;
            while(set.contains(x)) { // 수가 set에 있을 때 까지
                count++; // 수열 길이 증가
                x++; // 수 증가
            }
            answer = Math.max(answer, count);
        }
        return answer;
    }
    public static void main(String[] args) {
        System.out.println(MCNSS.solution(new int[]{8, 1, 9, 3, 10, 2, 4, 0, 2, 3}));
        System.out.println(MCNSS.solution(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0}));
        System.out.println(MCNSS.solution(new int[]{3, 3, 3, 3, 3, 3, 3, 3}));
        System.out.println(MCNSS.solution(new int[]{-3, -1, -2, 0, 3, 3, 5, 6, 2, 2, 1, 1}));
        System.out.println(MCNSS.solution(new int[]{-5, -3, -1, -4, 3, 3, 5, 6, 2, 2, 1, 1, 7}));
    }
}

결과