[JAVA] 백준 알고리즘 14225번 (부분수열의 합)

문제

---

이번에 다뤄볼 문제는 14225번 문제 '부분수열의 합'입니다.

문제에서 연습해야 하는key-point는 비트마스크입니다.

 

우선 비트마스크가 무엇인지 알아보겠습니다. 비트마스크는 알고리즘 기법을 뜻하는건 아닙니다. 컴퓨터 과학에서 마스크(mask) 또는 비트마스크(bitmask)로 불리우는 개념은 특히 비트 필드에서 비트 연산에 사용되는 데이터를 뜻합니다.

즉, 2진수 형태의 비트에서 각 포지션별로 true(1), false(0)가 마스킹 된 데이터를 비트마스크라고 생각하면 됩니다.

 

비트 연산으로는 기본적으로

AND연산(&), OR연산(|), XOR(^)연산, NOT연산(~), 쉬프트연산(<< / >>)이 존재하며

우리는 오늘 비트마스크 그리고 AND연산과 쉬프트연산을 활용하여 문제를 해결해보겠습니다.

 

문제에서 입력으로 N의 크기를 갖는 수열 S가 주어집니다.

예제 입력을 살펴보면 3의 크기를 갖는 수열 [5, 1, 2]가 입력으로 주어지게 되는거죠.

우리는 여기서 "부분수열의 합"으로 만들수 없는 수 중 가장 작은수를 찾아내야 합니다.

 

아래 해답 코드를 보면 입력을 받은 후 이중 포문으로 들어가게 되는데요.

여기서 바깥 포문의 의도가 무엇인지 파악하는게 중요합니다.

우리가 구하고자 하는것은 "부분수열의 합" 입니다.

이 바깥쪽 포문이 "부분수열의 모든 경우의 수"를 만들어내는 반복문임을 이해하는것이 중요합니다.

즉, 3의 크기를 갖는 수열 S를 입력 받았다면, 3개의 숫자를 활용하여 만들수 있는 모든 경우의 수

000

001

010

011

...

111

까지 진행되는 0 ~ 8(2^3 )의 이진수 형태인 비트마스크를 생성하게 되고

두번째 내부 반복문에서는 쉬프트연산과 AND연산을 통해 각 부분수열마다 생성되는 부분수열의 합을 만들어냅니다.

 

예를들어 첫번째 반복문에서 i가 5인경우를 살펴보겠습니다.

i가 5라는 것은 5의 이진수 형태인 비트마스크 101의 부분수열 합을 구하겠다는 의미입니다.

101이라면 [5, 1, 2]의 수열 중 5와 2의 합인 7을 얻게된다는 의미이고 이 과정은 두번째 반복문에서 진행하게 될 것입니다.

5와 2의 합, 7을 얻기 위해서는 아래 연산을 활용해야 합니다.

if((i & (1 << j)) != 0){
    createdNumber += sequence[j];
}

여기서 분기문에 존재하는 i & (1 << j) 에 대해 좀 더 자세히 설명 드려보겠습니다.

현재 i는 5이며 j는 반복문을 통해 0 ~ n-1까지 증가합니다. n이 3일 경우

5 & (1 << 0)

5 & (1 << 1)

5 & (1 << 2)

이처럼 3가지 경우가 생길 것이고 1 << j 란, 1을 이진수로 표현했을때

이진수 값을 왼쪽으로 j만큼 이동시키라는 의미이므로 이를 다시 표현하면 아래와 같습니다.

101 & 001

101 & 010

101 & 100

AND연산(&)의 경우 둘 다 true(1)일때 true(1)를 반환하기 때문에

101 & 001 = 001

101 & 010 = 000

101 & 100 = 100

각 연산을 마치면 위와 같은 값을 갖게 되고 입력받은 수열 [5, 1, 2] 중 001 위치와 100 위치에 있는
5와 2의 합인 7이 부분수열의 합으로 기록되게 됩니다.

 

이 과정을 반복 후 CAN_MAKE_NUMBERS에 true로 마킹되지 않은 가장 작은 수를 출력함으로써 문제를 해결하게 됩니다.

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

코드(JAVA)

import java.util.Scanner;

public class Main {

    static boolean[] CAN_MAKE_NUMBERS = new boolean[2000001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] sequence = new int[n];
        for (int i = 0; i < n; i++) {
            sequence[i] = sc.nextInt();
        }

        for(int i=0; i < (1 << n); i++){
            int createdNumber = 0;
            for(int j=0; j < n; j++){
                if((i & (1 << j)) != 0){
                    createdNumber += sequence[j];
                }
            }
            CAN_MAKE_NUMBERS[createdNumber] = true;
        }

        for(int i=1; i < CAN_MAKE_NUMBERS.length; i++){
            if(!CAN_MAKE_NUMBERS[i]) {
                System.out.println(i);
                break;
            }
        }
    }
}

 

14225번: 부분수열의 합