2629 - 양팔 저울

2629 - 양팔 저울 풀이입니다.

KOI 2001 초등부 2번

2가지 방법이 있네요. 저는 동전 교환 알고리즘(DP) 로 풀었습니다만, 대회 공식 풀이를 보니 휴리스틱을 추가한 재귀로 설명하네요. 구현의 차이일 뿐, 기초적인 발상은 똑같은 것 같습니다. 우선 글 주변이 없는 관계로 의식의 흐름 순서로 설명하는 점 양해를 구하겠습니다.

우선 문제에서 주어지는 조건들을 파악했습니다. 주어지는 추는 30개 이하이고, 모두 자연수이며, 같은 무게가 여러 개일 수 있습니다. 그리고 추는 500g 이하네요.

"주어진 추를 사용해서 구슬의 무게($x$ 라고 합시다.) 를 확인할 수 있는 가" 를 좀 더 수식처럼 바꿔보자면, 각 추를 $a_0, \dots a_n$ 으로 표현했을 때, $x = a_0 * (0|1) + \dots + a_n * (0|1)$ 처럼 쓸 수 있을것 같네요. 여기서 (0|1) 은 사용하지않거나/사용하거나를 의미하는 수입니다.

근데 이 수식은 뭔가 부족하네요. 주어진 추로 $x$를 만들 수 있는가를 묻고 있지만, 구슬($x$)와 같은 쪽에 추가 달려있을 경우는 고려되지 않았네요. 다음처럼 바꾸면 해결됩니다.

$$x = a_0 * (-1|0|1) + \dots + a_n * (-1|0|1)$$

방정식의 좌변/우변을 저울의 왼쪽/오른쪽으로 생각하면 좀 읽기 편해질겁니다. -1은 구슬과 같은 쪽에 매달았다는 뜻이 되는거죠.

이제 이 수식에 대한 답을 어떻게 구하는 가가 문제인데, $a_0, \dots a_n$을 하나씩 살피면서, 각 $a_i$($i$번째 추)에 대해

• 구슬과 같이 올렸을 때(-1)
• 올리지 않았을 때(0)
• 반대쪽에 올렸을 때(+1)

이렇게 3가지 행동 중 1개를 취할 수 있습니다. 예를 들어, $a = \{1, 4\}$ 라면 아래와 같은 경우의 수가 있겠네요.

저울의 중심 = |
 x   | 1
 x   | 4
 x   | 1 4
 x 1 | 4
 x 4 | 1

그렇다면 나올 수 있는 조합의 갯수는 $3^n$ 이겠군요! 주어진 추들로 만들 수 있는 모든 $x$를 구하면 되지 않을까요? 네. 이대로 돌린다면 안됩니다. $n$ 이 30개 이하니까 $3^{30}$. 대충 계산해도 $10^{14}$ 가 넘어가는 대수라 시간초과가 분명합니다.

참고로, 약 $10^8$번의 연산을 1000MS로 어림잡아 계산할 수 있습니다. (이것은 정확한 수치가 아니라 컴퓨터의 성능이나 환경에 따라 다릅니다! 시간 측정의 도움을 주는 척도로만 사용하세요.)

그럼 이 문제를 어떻게 해결할까요?

동전 교환 알고리즘(Coin Change Algorithm) 을 통해 해결할 수 있습니다. 간략히 설명하자면, "특정 단위의 동전들이 몇개 주어졌을 때, 이 동전들을 사용해서 x원을 만들 수 있는가?" 를 해결하는 알고리즘입니다.
이걸 이용해 모든 경우를 구한다면 이렇게 해결할 수 있습니다.
예시를 그대로 사용하겠습니다. 먼저, 1g짜리 추를 사용해 확인할 수 있는 경우 추의 무게는 (0g+1g/ 0g / 0g-1g) 입니다. 여기서 얻어진 -1g/0g/1g 에는 "1g짜리 추를 사용했다"라는 의미가 들어있습니다. 따라서 여기에 추가적으로 4g에 대해 살핀다면 "1g짜리와 4g짜리를 사용하여"와 같이 의미가 중첩되는 것입니다.
확인할 수 있는 추의 무게를 가진 배열을 $C$ 라고 하겠습니다. 그럼 $C$에는 처음에는 0g 이 들어있을 것입니다.

$$C = \{ 0 \}$$

1g짜리 추를 사용하여 결과를 확인한 후에는 다음과 같습니다.

$$C = \{ -1, 0, 1 \}$$

각 수들에 대해 4g 을 확인한다면

$$C = \{ -5, 3, -4, 4, 5, -3 \}$$ 과 같습니다.

 여기서 수를 정렬하지 않은 것은, -5, 3은 -1로부터. -4, 5는 0 으로부터 나왔기 때문입니다.  즉, -5 = -1-4(1g과 4g을 구슬과 같은 쪽에) 이고 3 = -1+4(1g은 구슬과 같은 쪽, 4g은 반대 쪽)를 의미합니다.

이 문제에서 사실 우리는 음수를 고려할 필요가 없습니다. 왜냐하면 (위에서 표현한 대로 저울을 표현하자면) x 1 | 4 와 4 | x 1 는 같기 때문입니다.
이런 식으로 점차 추의 무게를 키워가며 확인한다면, 모든 추의 무게를 확인할 수 있습니다.
나올 수 있는 최대 무게는 500g의 추가 30개인 15000g입니다.

요약

어떤 추의 무게를 $x$라고 하면, 왼쪽에 올리면 $x$가 빼지고 오른쪽에 올린다면 $x$가 더해지는 것으로 이해할 수 있다. 이것을 이용하여 주어진 추들로 확인할 수 있는 모든 구슬의 무게 를 구하고, 그 구슬의 무게에 대한 질답에 답한다.
적절한 가지치기 혹은 동전 교환 알고리즘을 통해 모든 경우의 수를 구한다.

더보기

동전 교환 알고리즘

• 2293번 - 동전 1
• Coin Change Problem
• Dynamic Programming | Set 7 (Coin Change) - GeeksforGeeks

#include <cstdio>
#include <algorithm>

inline int abs(int n){return n<0?-n:n;}

int main(){
    int i, j, n, a[30];
    scanf("%d", &n);
    for(i=0; i<n; ++i) scanf("%d", &a[i]);
    // std::sort(a, a+n);
    
    bool can[15001]={}, temp[15001]={};
    temp[0] = can[0] = true;
    
    for(i=0; i<n; ++i){
        for(j=0; j<=15000; ++j){
            if(can[j] == true){
                int left=abs(a[i]-j), right=abs(a[i]+j);
                if(left >= 0 && left <= 15000) temp[left] = true;
                if(right >= 0 && right <= 15000) temp[right] = true;
                temp[ a[i] ] = true;
            }
        }
        for(j=0; j<=15000; ++j) can[j] = temp[j];
    }
    
    int m, p;
    scanf("%d", &m);
    while(m--){
        scanf("%d", &p);
        printf( p <= 15000 && can[p] ? "Y ":"N " );
    }
    
    return 0;
}