사악한 드래곤을 무찌르는 방법 찾기 문제 (드림웍스 입사)

지난 번 문제와 함께 이번에도 풀어보는 드림웍스 입사 관련 문제, 사악한 용을 처단해야 하는데 아주 신기하게도 머리를 자르면 머리가 다시 자라고 꼬리를 자르면 꼬리가 자라는 용이 있다. 이 용을 처단하는 가장 빠르고 확실한 좋은 방법을 찾아야 하는데 총 몇 번의 검을 휘둘러야 용을 죽일 수 있는지 묻는 문제다.

3개의 머리와 3개의 꼬리를 가지고 있는 사악한 드래곤이 있다. 당신은 지식의 칼로 드래곤의 모든 머리와 꼬리를 잘라서 용을 무찔러야 한다. 검을 한 번 휘두르면 머리 또는 꼬리를 각각 한 개 혹은 두 개 자를 수 있다. (최대 2개를 한 번에 자를 수 있음, 단 머리와 꼬리를 동시에 같이 자를 순 없다) 하지만 머리 하나를 자르면 새 머리가 자라고, 꼬리 하나를 자르면 꼬리 두 개가 자라난다. 또 꼬리 두 개를 자르면 새로운 머리가 자라고, 머리 두 개를 자르면 아무것도 자라지 않는다. 그렇다면 총 몇 번의 검을 휘둘러야 사악한 드래곤을 무찌를 수 있을까?

이것이 오늘의 문제!

자르면 새로 자라고 자르면 새로 자라고 하는 방식이라 접근법이 중요할 것 같다. 특히 머리 1개를 자르는 경우에는 새 머리가 다시 자르기 때문에 신중할 필요가 있다, 아무 의미없는 행동이 될 수 있기 때문이다. 검을 휘두르는 횟수만 증가할 뿐 용에게 변화가 없기 때문이다. 이 말은 곧 마지막에는 머리 1개를 남기면 안된다는 뜻이 된다 (머리 1개만 남게 되면 무한 반복, 결판이 안난다)

이 문제를 보고 참 재미있는 발상이라고 생각했다, 머리와 꼬리 중에 무얼 잘라야 하고 어떻게 만들어 가야 하는지 그 과정이 꽤 중요한데 내 경우에는 무엇보다 최종적으로 머리를 남겨야 하고 그게 최소 2개, 혹은 짝수로 되어야 상황 종료가 가능하다는 예상하에 도전해 봤다. 이어서 바로 답풀이가 진행되니 답 공개는 바로 아래

꼬리 1개 자르면 꼬리 2개가 자라고 꼬리 2개를 자르면 머리 1개가 생긴다 - 내가 주목한 부분

1. 일단 머리 2개를 자르면 새로 자라는게 없기에 머리 2개부터 처단한다 (꼬리 3개, 머리 1개가 남음)

2. 꼬리 2개를 자른다 (머리가 새로 자라게 되어 꼬리 1개, 머리 2개가 됨)

3. 남은 꼬리 1개를 자른다 (꼬리가 다시 2개 생성되니 꼬리 2개, 머리 2개가 됨) 

4. 꼬리 2개를 자르면 꼬리는 모두 사라지지만 머리에서 막히게 된다, 꼬리 1개 혹은 머리 2개가 선택지인데 어차피 꼬리는 꼬리를 잘랐을 때에만 변수가 있기 때문에 자르지 않을 수가 없다, 나중이든 지금이든 결국 꼬리 1개는 무조건 잘라야 한다, 결국 꼬리 1개 자르기 선택 (꼬리 1개에서 새로 2개가 자라 꼬리는 3개, 머리 2개)

이쯤되면 꼬리를 이용해 머리를 2, 4, 6처럼 짝수로 만들기만 하면 된다는 논리가 성립

5. 꼬리 2개를 다시 자르고 (꼬리 1개, 머리 3개)

6. 다시 남은 꼬리 1개를 자르면 새 꼬리 2개가 생성 (꼬리 2개, 머리 3개)

7, 꼬리 2개를 마저 다 잘라버리면 (꼬리 0개, 머리 4개)

드디어 꼬리는 모두 없애고 머리는 짝수로 남겼다.

8. 머리 2개 잘라주고

9, 나머지 머리 2개 모두 잘라주면 끝, 총 9번

사실 난 이 문제를 풀고도 틀린 답이라고 생각했다. 용을 죽이는 방법도 물론 중요하지만 검을 적게 휘둘러야 한다는 최소 수만 놓고 보면 너무 검을 쓴 횟수가 많았기 때문이다. 5회 미만이어야 약간 아름다운 정답일 것 같은데 9번이나 쓰면 너무 많이 쓴 셈이다. 그래서 다른 방식으로 도전해 봤는데 답이 생성되지가 않는다. 결국 내 나름의 답만 찾은 상태에서 포기하고 답을 봤더니 ....허걱 9번이 정답 맞다. 물론 접근 방식에서 엄청난 차이를 보였고 나는 뱅뱅 돌아서 풀었지만 타일러의 답은 알흠다움 그 자체

꼬리 1개 자르면 2개가 된다는 점에 착안, 꼬리 3개를 자르면 총 6개로 바뀌고 꼬리 2개를 자르면 머리가 생성된다는 걸 이용해 꼬리 6개를 머리 3개로 변환 시킨다, 머리가 짝수가 되면 끝낼 수 있다는 걸 마찬가지로 이용해 기존 머리 3개와 새로 만든 머리 3개, 합 6개의 짝수 머리를 완성하고 2개씩 나누어 자르면 클리어가 되는 간단 접근, 짝수 머리 만들기에 집중해야 한다는 건 나도 알고 있었지만 한꺼번에 다 바꿀 수 있는 걸 하나씩 왔다갔다 한 내 답보다 확실히 깔끔하고 아름답다

최소 횟수에 집중한 나머지 너무 어렵게 생각하게 만든게 이 문제의 뽀인트, 3번, 혹은 5번 정도의 짧은 검의 횟수로 용을 죽일 수 있어야 한다는 관념에 사로잡혀 최소 수에 집착하다보면 답을 찾고도 제시하지 못할 때가 있는데 이 문제가 바로 그 부분까지 내포하고 있는 문제라고 이해하면 된다. 상대가 6번이라고 하면 그 보다 적은 5번으로 가능한 방법을 찾으려고 노력하기 쉬운데 이 문제는 몇 번의 검을 휘둘러야 용을 무찌를 수 있느냐를 묻는 문제이지 용을 무찌를 때 쓴 검의 횟수가 가장 적은 경우를 묻는게 아니다. 다른 사람들이 빨리 풀지 못한 건 바로 최소 수에 집착했기 때문. (일정 횟수가 넘어가면 최소 수가 아니라고 생각해 접근하던 방식을 포기하고 다시 시작)