[백준 1182] 부분수열의 합 (Python, Java)

김용범·2024년 12월 28일

문제 💁🏻‍♂️

해결 과정

처음 문제를 읽었을 때, 너무 간단하다고 생각해서 문제를 풀이했고, 결국 틀렸다.

사고 과정 (1) ❗️

그 이유는 부분수열의 뜻을 제대로 이해하지 못하고 있었기 때문이다. 나는 연속 부분수열로 이해하고 문제를 2중 for문을 사용한 브루트 포스 기법으로 풀이했기 때문에 빠르게 오답판정을 받았다. 개념을 정리해보자.

부분수열: 인덱스의 순서가 중복되는 것 없이 불연속이 가능한 오름차순을 가지는 수열
연속 부분수열: 인덱스의 순서가 중복되는 것 없이 연속적으로 오름차순을 가지는 수열

즉, 예를 들어 {1, 2, 3, 4} 라는 수열이 있을 때,

부분수열: {1, 3}, {1, 4}, {1, 2, 4} 등이 부분수열이다.
연속 부분수열: {1, 2, 3}, {3, 4} 등이 연속 부분수열이다.

사고 과정 (2) ‼️

문제를 정확히 이해하고 나서는 다시 어떻게 문제를 해결할 지 생각해보았다.

N의 범위가 1 ≤ N ≤ 20 으로 크기가 매우 작다.
주어진 수열에서 음수가 존재하므로, 결국 끝까지 탐색을 시도해봐야 한다.
2-1. 즉, 부분 수열에 대해서 {1, 2, 4}의 합이 7로 만족한다고 해서 끝나는 것이 아니라, {1, 2, 4, -1, 1} 과 같은 경우도 있기 때문에 끝까지 순회를 해봐야한다.
N개의 원소들 중에서 최소 1개부터 최대 N개를 뽑아 만들 수 있는 조합(순서 상관 x)이므로 백트래킹 기법을 통해 경우의 수를 모두 찾는다.
인덱스가 {1, 2, 3}, {2, 1, 3}, {3, 1, 2} 등 모두 같은 경우이므로, 시간복잡도를 줄이기 위해서 인덱스가 오름차순으로 결정된 것만 선택하도록 하자. 또한, {1, 1, 1,,} 과 같은 경우를 없애기 위해 방문 처리 배열 또는 리스트를 만들어서 중복되는 경우를 제외하자. (연습 - [ 백준 N과 M(2) 참고 ])

이와 같은 이유로 백트랙킹으로 문제를 재시도했다. 조합을 구하는 과정에서 인덱스 오름차순 처리, 중복 인덱스 제외와 같은 경우는 위에 적은 것과 같이 백준 N과 M(2) 문제를 풀어보면 익힐 수 있다. 비록 실버 3의 문제였지만, 여러가지 기법들을 연습해볼 수 있어 좋았다. 또한, 부분수열과 연속 부분수열의 개념을 정립할 수 있어서 괜찮은 문제인 것 같다!

TMI지만, 싸피에 입과하여 자바 코드로도 문제를 풀어봐야해서 파이썬과 자바 두 언어를 통해서 풀이했고, 코드를 모두 올려보았다. :)

코드

오답 코드 (문제 이해 x)

from sys import stdin

input = stdin.readline

n, s = map(int, input().split())
n_lst = list(map(int, input().split()))

cnt = 0
for i in range(n):
    SUM = 0
    for j in range(i, n):
        SUM += n_lst[j]
        if SUM == s:
            cnt += 1

print(cnt)

정답 코드 (Python)

from sys import stdin

input = stdin.readline


def bt(lst, total):
    global cnt

    # 크기가 양수이면서, 더한 값이 s가 되는 경우 -> cnt++
    if lst and total == s:
        cnt += 1

    for i in range(n):
        # 원소가 있고, 인덱스가 내림차순인 경우 -> 유망하지 않으므로 continue
        if lst and lst[-1] >= i:
            continue

        if not visited[i]:
            visited[i] = True  # 방문 처리
            lst.append(i)
            bt(lst, total + n_lst[i])
            lst.pop()
            visited[i] = False  # 복원 처리


n, s = map(int, input().split())
n_lst = list(map(int, input().split()))

cnt = 0
visited = [False for _ in range(n)]
bt([], 0)

print(cnt)

정답 코드 (Java)

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int n, s, cnt = 0, total = 0;
    static int[] arr;
    static boolean[] visited;
    static ArrayList<Integer> lst = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        arr = new int[n];
        visited = new boolean[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        bt(lst, total);
        System.out.println(cnt);
    }

    private static void bt(ArrayList<Integer> lst, int total) {

        // 크기가 양수이면서, 부분 수열의 합이 s인 경우 -> cnt++a
        if (!lst.isEmpty() && total == s)
            cnt++;

        for (int i = 0; i < n; i++) {
            if (!lst.isEmpty() && lst.get(lst.size() - 1) >= i)
                continue;

            if (!visited[i]) {
                visited[i] = true; // 방문 처리
                lst.add(i);
                bt(lst, total + arr[i]);
                lst.remove(lst.size() - 1);
                visited[i] = false; // 복원 처리
            }
        }
    }
}