Baekjoon(백준) 2629번 - 양팔저울
백준 사이트의 2629번.
문제 제목 : 양팔저울
백준 2629
한국정보올림피아드 (KOI) 2001년도 초등부 2번 문제이다.
사실 최근의 KOI 문제에서는 초등부 2번 정도면 10분 컷인데, 아주 옛날의 (내가 태어나기도 전의) 문제이다 보니 초등부 2번이라도 10분 컷은 아니다. (KOI는 옛날 문제일수록 어려운 경향이 있다)
문제 해석
추의 무게가 오름차순으로 정렬되어 주어진다. (같은 무게가 여러 개면 여러 번 반복되어 주어진다) 그 추들을 양팔 저울에 올려서 구슬의 무게를 측정한다. ‘측정 가능한지 확인할 구슬의 무게’들을 입력으로 받는다. 각각의 구슬 무게에 대해 주어진 추들과 양팔 저울로 측정이 가능한 무게인지 체크해서 가능하면 Y, 불가능하면 N을 출력한다.
좀 더 수학적으로 쓰면 주어진 추의 무게가 $a_0 , a_1 , … , a_n$ (추의 개수는 n+1 개) 일 때 ‘측정 가능한 구슬의 무게’는 다음과 같이 표현될 수 있어야 한다.
$\sum_{i=1}^{n} c_i a_i (c_i =$ 0 or -1 or +1)
즉 위의 식으로 만들 수 있는 값은 모두 ‘측정 가능한 구슬 무게’ 이다.
풀이 전략
dynamic programming을 이용한다. cache를 다음과 같이 정의한다.
cache[x][y] = 1 : $a_0, … , a_x$ 의 추를 이용해서 무게 y를 만들 수 있다.
그리고 cache[i][$a_i$]=1로 initialize 하고, cache[i][0] = 1로 initialize 해준다. 이후에는 recursive function으로 dfs search를 해준다. 이 그림을 보면 어떤 방식으로 search 하는지 보일 것이다.
위의 그림의 느낌대로 recursive function으로 구현하면 된다! 근데 여기서 탐색 시간을 줄이기 위해서 cache와 boundary condition을 잘 이용한다.
dfs로 탐색을 하다가 cache가 이미 1인 노드를 만나면 체크하던 구슬의 무게와 탐색을 하는 과정에서 거쳐온 노드의 cache가 모두 1이라는 것을 의미한다. 즉 cache가 1인 것을 만나는 순간, 역추적해서 root~해당 node 까지의 path에 있는 모든 노드의 cache를 1로 만들어줘야 한다. 또한, 그 구슬의 무게는 측정 가능한 것이다.
또한, boundary condition은 recursive function의 parameter에서 무게가 (모든 추의 무게합)을 초과하거나, 이미 visit 한 노드일 때, cache 가 이미 1일 때, cache가 0인데 현재 parameter에서 추의 index가 0 (마지막) 일 때이다. 그거를 잘 고려해준다면 어차피 아무리 많이 탐색해보아야 $30*40000=1200000$ 개 내에서 모두 탐색이 되기 때문에 시간 초과될 일이 없다.
구현
구현 방법에 대해서는 앞에서 이미 충분히 설명했다. 특별히 구현할 때 주의할 점은 다음으로 정리될 것 같다.
- 매번 체크하는 구슬의 무게가 달라질 때마다 visited를 초기화하는 것
- 미리 cache를 초기화 해놓고 initialize 하는 것
- 탐색을 하다보면 recursive function parameter의 무게가 음수가 되는 경우가 있다. 잘 생각해보면 이는 의미 없는 값이 아니라 그 값에 절댓값을 씌운 무게를 만들 수 있다는 것을 의미한다. 놓치기 쉬운 부분이다.
- recursive function을 최대한 헷갈리지 않고 깔끔하게 구현해낼 수 있으면 좋을 것 같다.
뭐 그렇다. 초등부 2번 치고는 좀 어려운 문제인 것 같았는데 적고보니 recursive function만 잘 활용하면 그렇게 어려운 문제가 아닌 것 같기도 하다.
자세한 solution code는 github에 있다.
Leave a comment