[백준] 2437번 - 저울 (C++/파이썬)

문제) 백준 - 그리디 알고리즘 (Greedy) - 저울

2437번: 저울

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓

www.acmicpc.net

문제를 오랜 시간 관찰했지만... 누적합이라는 느낌은 왔지만 알고리즘의 핵심을 찾지 못했다. 결국 3일 고민후, 답을 봤지만... 이건 뭐 풀이가 이해가 가지 않았다. 수학적 귀납법스러웠는데 쉽게 납득이 되지 않았다. 그러던 중 엄청난 풀이를 발견했다.

백준 2437 풀이 및 해설

개요 매우 복잡해보이는 문제가 그림으로 풀면 매우 단순하게 풀리는 경우 는 그리 드문일이 아닙니다. 이 문제는 수학적 귀납법으로도 풀 수 있지만, 수직선을 사용하면 훨씬 직관적이고 쉽게

aerocode.net

1	2	3
1	2	3	X	5	6	7	8

위의 표를 보면 1~3까지 측정 가능하다고 하자. 만약 무게가 5짜리 추가 들어온다면, 우리는 1~3까지 측정 가능했으니 그 범위에 5를 더하면 된다. 이렇게 되면 4에 해당하는 범위에 비어버리므로 답은 4가 된다.

이 게시물을 보고 묵은 때가 내려간 느낌이였다. 수직선을 이용한 다른 해석인데 보면서 경이로운 수준이었다.(물론 내 실력이 *밥이기도 하고...)

저 핵심을 바탕으로 다시 코드를 짜니 너무 간단한 문제.

C++ 소스 코드)

파이썬 소스 코드)

댓글