[코딩 인터뷰 완전 분석 6E] "무거운 알약"

Question. 코딩 인터뷰 완전 분석 6E - 06. 수학 및 논리 퍼즐 - 무거운 알약

 

약병 20개가 있다. 이 중 19개에는 1.0그램짜리 알약들이 들어있고, 하나에는 1.1그램짜리 알약들이 들어 있다.
정확한 저울 하나가 주어졌을 때, 무거운 약병을 찾으려면 어떻게 해야 할까? 저울은 딱 한 번만 쓸 수 있다.

 

---

Answer.

 

저울을 딱 한 번만 쓸 수 있다는 것이 강한 제약조건이다.

그렇기 때문에 한 번 저울을 사용할 때 가능한 많은 알약들을 사용해야 한다.

 

약병에서 알약을 뽑는 개수를 달리 함으로써 이를 약병의 index로 사용하면, 

나온 무게를 보고 약병의 index를 알 수 있다.

 

예를 들어 문제를 단순화해서 약병이 2개 있다고 가정해보자.

하나는 1.0그램짜리 알약이 들어있고, 또 하나는 1.1그램짜리 알약이 들어있다.

이때 똑같이 1개, 1개씩 뽑는다면 무게를 쟀을 때 2.1g이다.

하지만 이 무게를 보고 어느 병에 1.1그램이 들었는지 알 길이 없다.

똑같이 1개, 1개씩 뽑았기 때문이다.

 

하지만 뽑는 개수를 달리해봤다고 하자.

한 병은 1개 뽑고, 또 다른 한 병은 2개 뽑았다고 하면, 

나올 수 있는 무게는 2.1g 이거나 2.2g일 것이다.

 

1) 1.0g 2개, 1.1g 1개 -> 2.1g

2) 1.0g 1개, 1.1g 2개 -> 2.2g

 

즉, 나온 결과를 보고 1.1g이 어디 들었는지 알 수 있다.

2.2g이 나왔다면 1.1g은 약을 2개 뽑은 병이고 

2.1g이 나왔다면 1.1g은 약을 1개 뽑은 병이다.

 

이와 같이 각 병에서 뽑는 약의 개수를 달리하면, 

무게 역시 다 달라지기 때문에 어떤 병에 1.1g이 들었는지 알 수 있다.

 

이를 수식으로 나타내면, (전체 무게 - 210) / 0.1 이다.

 

이 식을 코딩한 것이 아래와 같다.

소수 처리와 나누기 처리 하는 것이 좀 까다로웠다. round를 이용하고 *로 바꿔 풀었다.

from random import randint

"""
This code is simulation code of below question.

Q. 무거운 알약: 
약병 20개가 있다. 
이 중 19개에는 1.0그램짜리 알약들이 들어있고, 하나에는 1.1그램짜리 알약들이 들어 있다. 
정확한 저울 하나가 주어졌을 때, 무거운 약병을 찾으려면 어떻게 해야 할까? 
저울은 딱 한 번만 쓸 수 있다.
"""

def simul(n, data):
    total = 0
    for i in range(1, n+1):
        total += data[i] * i
    return total

def sum_n(n):
    return n * (n + 1) // 2

def solve(n, data):
    # return int((simul(n, data) - int(n*(n+1)//2)) / 0.1)
    return int(round(simul(n, data) - sum_n(n), 2) * 10)   # 수식: (전체 무게 - 210) / 0.1


if __name__ == "__main__":
    # make data
    n = 20
    data = [1]*(n+1)
    expected = randint(1, 20)
    data[expected] = 1.1

    # answer
    actual = solve(n, data)
    print(data)
    print(f'Expected: {expected}\nActual: {actual}')
    assert expected == actual

 

 

 

sol 1)
Time Complexity	O(1)
Space Complexity	O(1)