[코드트리 파이썬] 삼 오 무

문제

 

---

풀이

이분탐색을 이용해 해결하였다.

임의의 숫자 하나를 정한 후 해당 숫자가 우리가 구하려는 답보다 큰지 작은지만 판별하면 된다.

 

주어진 N은 Moo값을 건너뛴 숫자이므로

1, 2, Moo, 4, Moo, Moo, 7 의 순서로 진행하였을 때

N이 4라면 답은 7이된다.

따라서 N이 주어졌을 때 내가 가진 숫자가 N이 가리키는 숫자보다 큰지 작은지 판별한다.

 

판별법은 다음과 같아

Moo는 3과 5의 배수로 진행한다.

임의의 값이 주어졌을 때 해당값을 3으로 나눈 나머지는 1부터 해당 값까지의 숫자 중 3의배수의 숫자의 개수이므로

임의의 수를 3으로 나눈 나머지와 5로 나눈나머지를 뺀 후 공통된 15로 나눈 나머지를 더한 뒤 나온 수를

N값과 비교하여 판단하면 된다.

예를들어 주어진 N은 4 즉 7을 가리키고 있을 때 위의 방법을 5에 적용시키면 3이나온다. 이 3은 4보다 작으므로 

5는 N = 4일 때 수 즉 7보다 작다는 것을 알 수 있다.

 

def isPossible(target):
    compare = 0
    compare += target // 3
    compare += target // 5
    compare -= target // 15

    compare = target - compare

    

    if compare >= N:
        return True
    else:
        return False

해당 아이디어를 구현한 결과이다.

위의 공식을 적용한 compare값을 N과 비교하여 return값을 결정한다.

 

while left <= right:
    mid = (left + right) // 2

    if isPossible(mid):
        right = mid - 1
        res = min(res, mid)
    
    else:
        left = mid + 1

비교한 값을 받아 true인 경우 즉 N값보다 크거나 같은경우 N값에 가까워야 하므로 최소값을 갱신해준다.

 

 

---

코드

import sys
N = int(input())
left = 1
right = sys.maxsize
res = sys.maxsize

def isPossible(target):
    compare = 0
    compare += target // 3
    compare += target // 5
    compare -= target // 15

    compare = target - compare

    

    if compare >= N:
        return True
    else:
        return False


while left <= right:
    mid = (left + right) // 2

    if isPossible(mid):
        right = mid - 1
        res = min(res, mid)
    
    else:
        left = mid + 1

print(res)