백준 1187 자바, C++ - 숫자 놀이 (boj 1187 java c++)

문제 : boj1187

 

 

  감을 제대로 못잡고 있었는데, '수학귀신' 책을 추천해줬던 수학 잘하는 선배같은 동생의 도움으로 풀 수 있었다.

 

1. 귀납법(귀납 추론)으로 풀 수 있는 문제이다.

1.1 k=1

  k를 1부터 증가시켜 나가면서 생각해보자. 우선 k=1일 때, N은 2가 된다. 이 때 2*2-1 = 3개 중 합이 2로 나누어 떨어지는 2개를 뽑는 문제가 된다. 그럼 2*2-1개의 수가 어떻게 나와야 2로 나눌 수 있는 2개를 뽑을 수 있을까? 이 때 모든 경우를 나타내보면 다음과 같다.

 

A. 3개의 수가 모두 짝수일 경우 -> 아무거나 2개 뽑으면 된다.

B. 3개의 수가 모두 홀수일 경우 -> 아무거나 2개 뽑으면 된다.

C. 3개의 수가 짝수2개, 홀수1개인 경우 -> 짝수 2개를 뽑으면 된다.

D. 3개의 수가 짝수1개, 홀수2개인 경우 -> 홀수 2개를 뽑으면 된다.

 

  즉, k=1인 경우 어떠한 경우라도 3개의 음이 아닌 정수 중 2개를 뽑아 2로 나누는 경우를 찾을 수 있다.

 

1.2 k=2

  이제 k=2가 되고 그럼 N=4이다. 2*4-1 = 7개 중 4개를 뽑아 4로 나누어 떨어질 수 있어야 한다. 그런데 이 때, 7개에 대해 3개 중 2개를 고르는걸 반복하면 총 몇개가 나올까? [a,b,c,d,e,f,g]의 7개가 있을 때 a,b,c 중 앞의 2개를 뽑고 c를 남기자. 그다음 c,d,e 중 이번엔 c,e를 뽑고 d를 남긴다. 그다음은 d,f,g 중 뒤의 2개를 뽑고 d가 하나 남는다. 그럼 남은건 3개로, [a+b, c+e, f+g]가 될 것이다. 근데 이처럼 3개 중 2개를 뽑는걸 반복할 때, 합이 2로 나누어 떨어지는걸로 뽑았다고 해보자(그게 가능함은 '1.1'에서 항상 가능함을 보였었다.). 그렇다면 뽑힌 a+b, c+e, f+g는 2로 나누어 떨어지는 수 일 것이다.

 

  그럼 (a+b)/2 = a'+b' 이라 해보자. 그럼 a+b = 2(a'+b') 일 것이고, 마찬가지 방식으로 c+e = 2(c'+e'), f+g = 2(f'+g') 이다. 그렇게 하더라도 a'+b', c'+e', f'+g'은 여전히 정수이다. 그럼 '1.1'을 다시 반복해서, a+b, c+e, f+g의 3개 중 2개를 뽑은 것은 4로 나누어 떨어질 수 있을까? 만약 a+b와 c+e를 선택했다고 해보자. 그럼 a+b+c+e = 2((a'+b')+(c'+e'))이 될테고, (a'+b')+(c'+e')가 2로 나누어 떨어진다면 2(2((a''+b'')+(c''+e''))) 으로 해도 a''+b''+c''+e''은 정수일 것이므로 4로 나누어 떨어지는게 된다 ( (a'+b')/2 = a''+b'' 이다. ).

 

  즉, 정리해보면 7개를 매번 3개 중 합이 2^1로 나누어 떨어지는 2^1개씩 뽑는 과정을 거친다. 그럼 3개의 수가 나오고, 해당 수는 이미 2로 나누어도 정수인 수 이므로 '2로 나눈 상태에서 2로 나누어 떨어지는 수를 찾으면 그게 결국 4로 나누어 떨어지는 수를 찾는게 된다.'. 3개 중 2개의 정수를 뽑는 경우 무조건 2로 나눌 수 있는 경우가 나오니, 합이 4로 나누어 떨어지는 수 2개를 항상 찾을 수 있는게 된다.

 

1.3 k=3

  마찬가지다! k=3, N=8, 2*8-1=15개 중 8개를 뽑아 8로 나누어 떨어질 수 있어야 한다. 이 경우에도 마찬가지로

A. 15개의 수를 3개 중 합이 2^1로 나누어 떨어지는 2^1개를 골라 7개가 나온다.

B. 그 7개는 2로 나누어도 정수이다. 그러니 일단 나누었다고 생각해보자. 그럼 2로 나누어 떨어지는 수를 찾더라도 이미 2로 나눈 것이니 4로 나누어 떨어지는 수가 된다. 따라서 그 7개에 대해 '1.2'의 과정을 거치면, 이제 4로 나누어 떨어지는 수 3개가 나온다.

C. 이제 4로 나누어도 정수인 수 이므로 4로 나눈 후에도 합이 2로 나누어 떨어지는 수를 찾자. 그럼 합이 8로 나누어 떨어지는 수를 찾은게 된다. 또한 B에서 고른 수는 결국 그 내부에 4개의 수가 합쳐진 셈이니, 2개를 고르면 처음 입력에서 8개를 고르는게 된다.

 

 

1.4 ..... 이렇게 계속 반복된다.

  귀납법에 따라 3개 중 2로 나누어 떨어지는 2개를 항상 뽑을 수 있으므로 -> 7개 중 4로 나누어 떨어지는 4개는 항상 뽑을 수 있고 -> 15개 중 8로 나누어 떨어지는 8개는 항상 뽑을 수 있고 -> ... 2047개 중 1024로 나누어 떨어지는 1024개를 항상 뽑을 수 있다! 

 

즉, '답이 존재하지 않을 경우 -1을 출력한다.' 라곤 했는데 -1을 출력하면 무조건 틀린다 ㅋㅋ 아마 채점 프로그램에 'if (answer == -1) return WA; // WA; Wrong Answer' 이런게 있지 않을까 싶다.

 

 

2. 하지만 이 문제는 다이아 티어 문제다. 풀이가 생각났다고 구현이 호락호락하진 않다.

  내 경우엔 deque(이하 덱)를 사용해서 구현했다. k=3이라면, 15개를 전부 덱에 넣고 앞에서부터 3개씩 빼서 그 중 합이 2로 나누어떨어지는 2개를 아무거나 고르고 남은 1개는 덱의 앞에 다시 넣고, 합은 덱의 뒤에 넣는다. 그걸 처음 15개에 대해 전부 진행하고, 마지막에 남은 3개에 대해서는 남은 1개는 덱의 앞에 다시 넣지 않고 그냥 버리면 된다. 이제 그럼 2로 나누어 떨어지는 2개의 합 7개가 덱에 들어있다. 그걸 또 위의 과정을 똑같이 반복한다. 덱에서 앞에 3개를 빼고 이번엔 합이 4로 나누어떨어지는 2개를 찾고 합을 덱의 뒤에, 남은걸 덱의 앞에(마지막 남은 3개에 대해선 남은건 버리고)... 그럼 4로 나누어 떨어지는 값 3개가 남는다. 그럼 이제 또 덱의 앞에 3개를 빼서 합이 8로 나누어 떨어지는걸 찾는다. 이런식이다.

 

  예를들어 예제 입력 1에 대해 다음과 같이 동작한다. 저 배열같이 생긴걸 덱이라고 그린거다.

4
1 2 3 4 5 6 7

 

 

3. 근데 위처럼 합만 구하면 뭐함? 이 문제는 고른 N개의 수를 출력까지 해야하는데?

  이걸 위해 내 경우엔 비트 마스킹을 사용했다. 물론 최대 2047개니까 정수 하나로는 비트마스킹을 할 수 없다. int형이 일반적으로 4byte 이므로, 32 bit이다. 그럼 int형 64개가 있다면 2048개의 비트가 있으니, 처음 입력으로 들어온 인덱스 2048개를 모두 표현할 수 있다. 그럼 그 64개의 int에 대해 비트마스킹 로직을 세운다면, 덱에 들어가는 각 정수에게 이 정수가 처음 입력으로 들어왔던 2N-1개의 수 중 몇 번째 인덱스를 가진 녀석들을 합해서 만들어진 정수인지 기록할 수 있다. 이렇게 해도 덱에는 언제나 2047개 이하의 원소들만 존재할 수 있으므로 모든 원소마다 int 64개로 체크하더라도 2047*64*sizeof(int)=524,032byte=1MB도 안된다.

 

  예를들어 idx(0~최대2047)에 대해 'ingredients[idx/32] = 1<<idx%32;' 와 같이 하면 마치 2048개의 비트를 가진 하나의 정수에 대한 비트마스킹처럼 동작시킬 수 있다.

 

  최종적으로 덱에 하나 남은 최종 결과에 대해 비트마스킹을 체크하면 처음 입력으로 들어온 값들 중 몇 번 몇 번 idx가 쓰였는지 알 수 있고, 그걸 전부 출력해주면 된다. 코드(자바, C++ 두가지)를 참고하면 알 수 있을 것이다.

 

 

코드(자바) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

class Num {
    int num;
    int[] ingredients;
    public Num(int num, int idx) {
        this.num = num;
        ingredients = new int[64];  // 2*2^10/sizeof(int)
        ingredients[idx/32] = 1<<idx%32;
    }
    public Num(Num a, Num b) {
        num = a.num + b.num;
        ingredients = new int[64];
        for (int i = 0; i < 64; i++) {
            this.ingredients[i] = a.ingredients[i] | b.ingredients[i];
        }
    }
}

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[2*n-1];
        Deque<Num> dq = new ArrayDeque<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 2*n-1; i++) {
            int cur = Integer.parseInt(st.nextToken());
            arr[i] = cur;
            dq.add(new Num(cur, i));
        }
        int k = 1;
        int tmp = n;
        while((tmp>>=1) != 1) {
            k++;
        }
        for (int i = 1; i <= k; i++) {
            int limit = dq.size() / 2;
            for (int j = 0; j < limit; j++) {
                Num[] sel = {dq.pollFirst(), dq.pollFirst(), dq.pollFirst()};

                boolean chk = false;
                for (int y = 0; y < 2 && !chk; y++) {
                    for (int z = y+1; z < 3; z++) {
                        if ((sel[y].num + sel[z].num) % (1<<i) == 0) {
                            dq.addLast(new Num(sel[y], sel[z]));
                            if (j != limit-1) dq.addFirst(sel[3-y-z]);
                            chk = true;
                            break;
                        }
                    }
                }

            }
        }
        int[] answer = dq.poll().ingredients;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < answer.length; i++) {
            int idx = i*32;
            for (int j = 0; j < 32; j++) {
                if ((answer[i] & 1<<j) != 0) {
                    sb.append(arr[idx + j]).append(' ');
                }
            }
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

코드 (c++) : github

#include <iostream>
#include <deque>

using namespace std;

class Num {
public:
    Num() {

    }

    int num;
    int ingredients[64] = {0, };

    Num(int num, int idx) {
        this->num = num;
        this->ingredients[idx/32] = 1<<idx%32;
    }
    Num(Num a, Num b) {
        this->num = a.num + b.num;
        for (int i = 0; i < 64; i++) {
            this->ingredients[i] = a.ingredients[i] | b.ingredients[i];
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    int arr[2048] = {0, };
    deque<Num> dq;

    int n, cur;
    cin >> n;
    for (int i = 0; i < 2*n-1; i++) {
        cin >> cur;
        arr[i] = cur;
        dq.push_back(Num(cur, i));
    }

    int k = 1;
    int tmp = n;
    while ((tmp>>=1) != 1) {
        k++;
    }
    for (int i = 1; i <= k; i++) {
        int limit = dq.size() / 2;
        for (int j = 0; j < limit; j++) {
            Num sel[3];
            sel[0] = dq.front();
            dq.pop_front();
            sel[1] = dq.front();
            dq.pop_front();
            sel[2] = dq.front();
            dq.pop_front();
            
            bool chk = false;
            for (int y = 0; y < 2 && !chk; y++) {
                for (int z = y+1; z < 3; z++) {
                    if ((sel[y].num + sel[z].num) % (1<<i) == 0) {
                        dq.push_back(Num(sel[y], sel[z]));
                        if (j != limit-1) dq.push_front(sel[3-y-z]);
                        chk = true;
                        break;
                    }
                }
            }

        }
    }

    Num ans = dq.front();

    for (int i = 0; i < 64; i++) {
        int idx = i*32;
        for (int j = 0; j < 32; j++) {
            if ((ans.ingredients[i] & 1<<j) != 0) {
                cout << arr[idx + j] << ' ';
            }
        }
    }
}