[240502] 알고리즘 리부트 58일차 - 백준 1182, 6603 자바

[Part2-Chapter05-Clip01]

- 백준 1182 부분수열의 합

재귀를 명확히 이해하고 있지 않다고 생각하게 된 문제였다. 일단 수열과 부분 수열의 정의에 대해서 알아야 하는데 수열은 일정한 규칙에 따라 순서대로 나열한 수의 집합이고 부분수열은 원 수열의 항의 일부분만을 딴 수열을 의미한다. 단, 이 때 수열은 원래의 순서를 유지해야 한다. 

예를 들어, {𝑎𝑛}=1,2,3,⋯ 라는 수열이 있다고 가정하자. 그럼, {𝑎𝑛𝑘}=1,3,6,8,⋯은 부분수열이지만, {𝑎𝑛𝑘}=1,3,2,6,7,⋯ 은 부분수열이 아니다. 

 

기본적으로 문제의 지시사항이 불친절하다고 생각한다. 주어지는 n개의 수의 나열이 수열의 형태로 주어지는지 아닌지를 말하지 않았는데 이게 중요한 이유는 아래 정렬 코드가 없으면 정답 처리가 되지 않기 때문이다. 일단 수열에 속한 순서가 섞인 수라는 가정하에 정렬을 해서 수열의 형태로 정리한 후에 부분 수열을 1개~n개까지 뽑아 s와 같은지 확인했다. 이 때 중요한 것은 1) 동일한 요소를 중복으로 선택하지 않는다. 2) (원수열의 순서를 유지한) 부분 수열이기 때문에 이전에 선택한 요소의 인덱스가 현재 선택하는 인덱스보다 앞서는지 확인해야 한다는 점이다. 

헷갈렸던 부분은 바로 2) 부분인데 위에서 말한 수열과 부분수열을 명확히 정의하지 않아서였다. 초반에 잘못 설정한 조건은 다음과 같다. 아래와 같이 이전에 선택된 숫자가 이번에 선택하려는 숫자보다 크다면 지나가도록 처리했는데 이러한 조건은 원 수열의 순서를 섞어서 뽑는 것을 허용하기 때문에 문제에서 요구하는 바와 다르다. 따라서 원소의 값이 아닌 인덱스를 비교해서 부분 수열을 만들어야 한다.

if (curr != 0 && selected[curr - 1] > target[i]) continue; (X)
if (idx >= i || visited[i]) continue; (O)

import java.util.*;
import java.io.*;

public class Main {

    public static BufferedWriter bw;
    public static BufferedReader br;
    public static StringTokenizer st;
    public static int[] target;
    public static boolean[] visited;
    public static int n, s, ans;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        target = new int[n];
        visited = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) target[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(target);

        ans = 0;
        for (int idx = 1; idx <= n; idx++)
            find(idx, 0, 0, -1);

        System.out.println(ans);
    }

    private static void find(int limit, int curr, int sum, int idx) {
        if (curr == limit) {
            //System.out.println("===========================다 찾음 sum: " + sum);
            if (sum == s) {
                ans++;
                //System.out.println("================더했음");
            }
            return;
        }


        for (int i = 0; i < n; i++) {

            if (idx >= i || visited[i]) continue;

            sum += target[i];
            visited[i] = true;

            //System.out.printf("현재 채울 인덱스 %d, 현재 선택한 값 %d, 해당 값의 인덱스 %d\n", curr, target[i], i);
            find(limit, curr + 1, sum, i);
            visited[i] = false;
            sum -= target[i];

        }
    }
}

 

[Part2-Chapter05-Clip02]

- 백준 6603 로또

이 문제는 비교적 조건과 입력 사항을 명확하게 제공하고 있다. 오름차순으로 정렬하기 때문에 방문 여부를 볼 필요 없고 모두 다른 수로 구성되어 있는 집합을 제공한다. 따라서 직전에 선택한 숫자와 비교해서 더 큰 숫자만 뽑아준다면 모든 경우의 수를 구할 수 있다.

import java.util.*;
import java.io.*;

public class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static StringTokenizer st;
    public static int[] ans, candi;
    public static int k;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (true) {
            st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());

            if (k == 0) break;

            candi = new int[k];
            for (int i = 0; i < k; i++) candi[i] = Integer.parseInt(st.nextToken());

            //System.out.println(Arrays.toString(candi));

            ans = new int[6];

            choose(0);
            bw.write("\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static void choose(int curr) throws IOException {

        if (curr == 6) {
            //System.out.println(Arrays.toString(ans));
            for (int i : ans) bw.write(i + " ");
            bw.write("\n");
            return;
        }

        for (int i = 0; i < k; i++) {

            if (curr != 0 && ans[curr - 1] >= candi[i]) continue;

            ans[curr] = candi[i];

            choose(curr + 1);

        }
    }
}