[Python3] 바퀴벌레 문제

예전에 한창 떠돌았던 문제였다. 문제에만 관심을 가지고 알고리즘을 짜보자. 우선, 문제를 다음과 같이 변형하였다.

 빈병 m개를 가져다 주면 콜라 1병을 준다고 한다. 빈병 n개를 가지고있을 때 몇병을 받을 수 있는가? 

필자는 이 문제를 딱 보고 그냥 n/m의 몫이 1미만이 나올때까지 n/m 몫의 합을 더한뒤 n에 n/m을 넣어주면 되는거 아닌가? 라고 생각하고 코드를 짰지만, 여러 테스트 케이스에서 실패했다. n/m의 나머지를 가지고 있다가 나중에 또 나머지가 생겼을경우 더해줄 수 있다는 것을 생각을 못했던 것이다.

문제가 잘 이해가 가지 않는 경우 n=20 m=2 라고 일단 생각하고 20개의 종이를 짤라 한면은  '안빈병' 다른 한면은'빈병' 이라 적자. 두개의 '빈병'을 하나의 '안빈병'으로 바꿔주고 '안빈병'을 '빈병'으로 뒤집은 갯수를 세면 된다. 여하튼 알고리즘은 다음과 같다.

첫 번째 줄에 n과 m을 입력 받는다.

total이라는 변수를 만들어 0을 할당시킨다.

n/m의 몫이 1보다 크거나 같으면 아래 코드를 실행시킨다.

total에 n/m의 몫을 더해준다.

n에 n/m의 몫과 나머지를 더해준다.

여기서 n은 빈병의 갯수이다. n/m의 몫은 빈병을 콜라로 바꾼 수 인데, 그걸 또 마셔버려 빈병이 된다. 여기에 갯수인 n/m의 나머지를 더해주면 된다.

n,m=input().split(" ")    #n과 m은 공백을 기준으로 순서대로 나뉜다.

n=int(n)

m=int(m)

total=0

while(n//m>=1):

total+=n//m

n= n%m+n//m    # '%'는 나머지를 '//'는 몫을 의미한다.

print(total)