누워서 읽는 알고리즘 p58-59 풀이

요즘 알고리즘을 공부하며 관련 책들을 읽고 있는데 재미있는 문제를 보게 되어 풀이 과정을 올려본다.

 

문제

서로 색이 다른 5채의 집이 있다. 각 집에는 출신 나라가 서로 다른 사람이 살고 있다. 각 집주인은 5가지 다른 종류의 음료수를 마시고 상표가 다른 담배를 피우며, 애완동물을 한 마리씩 기른다. 아래에 주어진 정보를 토대로 ‘금붕어’를 기르고 있는 사람인지 밝혀내라.

 

1. 영국 사람은 빨간 집에서 산다.
2. 스웨덴 사람은 강아지를 기른다.
3. 덴마크 사람은 차를 마신다.
4. 초록 집은 하얀 집의 바로 왼쪽에 붙어 있다.
5. 초록 집의 주인은 커피를 마신다.
6. 팔 몰을 피우는 사람은 새를 기른다.
7. 노란 집의 주인은 던힐을 피운다.
8. 정 중앙에 있는 집에서 사는 사람은 우유를 마신다.
9. 노르웨이 사람은 첫 번째 집에서 산다.
10. 블렌드를 피우는 사람은 고양이를 키우는 사람의 이웃이다.
11. 말을 키우는 사람의 집은 던힐을 피우는 사람의 옆집이다.
12. 블루 매스터를 피우는 사람은 맥주를 마신다.
13. 독일 사람은 프린스를 피운다.
14. 노르웨이 사람은 파란 집의 이웃이다.
15. 블렌드를 피우는 사람은 물을 마시는 이웃이 있다.

 

 

풀이

내 생각의 흐름대로 풀어보자면

• 노르웨이 사람이 첫 번째 집
• 노르웨이 옆집 파란집
• 정 중앙 우유
• 노란 집 던힐
• 던힐 피는 사람 옆집 말
• 남은 집은 두 채, 초록집은 커피를 마시는데 초록집 오른쪽에 흰 집이 붙어있으니 아래와 같은 집 순서

노	파	빨	초	흰
노르웨이		영국
		우유	커피
던힐
	말

• 블루메스터는 맥주, 덴마크는 차 니까 이 둘은 파, 흰 중의 한 집에만 들어갈 수 있음
• 따라서 남은 물은 노르웨이
• 블렌드는 물을 마시는 이웃을 두고 있으니 파란집
• 블렌드가 파란집 됐으니 자동으로 블루메스터, 맥주는 하얀집
• 맥주가 하얀집 갔으니 차와 덴마크는 파란집

노	파	빨	초	흰
노르웨이	덴마크	영국
물	차	우유	커피	맥주
던힐	블렌드			블루메스터
	말

• 독일사람은 프린스를 피운다 → 초록집
• 자동으로 빨간집은 팔 몰, 새
• 블렌드를 피우는 사람의 이웃 중 하나는 고양이를 키우는데 한쪽에서 새를 키우니 남은 한쪽은 고양이
• 스웨덴 사람은 강아지를 기른다 → 남은 흰 집에 스웨덴, 강아지

노	파	빨	초	흰
노르웨이	덴마크	영국	독일	스웨덴
물	차	우유	커피	맥주
던힐	블렌드	팔 몰	프린스	블루메스터
고양이	말	새		강아지

 

그럼 남은 초록집에서 금붕어

 

 

3분 안에 풀진 못했지만 그래도 금방 다 풀어냈다!

첫번째 표까지는 술술 풀렸지만 그 이후 어떻게 풀어야 할지 감이 안왔다.

그래서 경우의 수를 하나하나 적어보고 물의 위치를 알아낸 순간부터는 순식간에 푼 것 같다.

아직 책 초반인데 어떤 문제들이 나올지 기대된다.