[BOJ] 16785번, ソーシャルゲーム

백준 16785번은 solved.ac 가서 브론즈 IV 문제들 중에 눈에 띄는 거 아무거나 클릭했다가 걸린 문제다. 문제가 일본어로 되어있어서 당황했으나, 번역기 돌려보니 설명 자체는 간단.

 

- 출첵하면 A만큼 점수를 준다.

- 연속 7일 출첵하면 B만큼의 보너스 점수를 준다. 그리고 연속 출첵 카운터가 0일로 리셋.

- C점 이상이 되기 위해서는 연속 며칠 동안 출석해야 하는가?

 

그리고 인풋으로

A B C

가 주어진다.

 

7일 연속 출첵하면 받을 수 있는 점수가 7*A+B점이므로, C안에 7*A+B를 몇 번 집어넣을 수 있는지 체크하고 --(1), 7*A+B를 계속 빼고 남은 나머지 점수를 며칠 동안 출석하면 채울 수 있는지 찾으면---(2) 문제가 풀린다.

 

D = 7*A+B라고 두면, 

(1) C를 D로 나눈 몫을 구하고 7을 곱하면 몫*D점을 얻는 데에 걸리는 날을 알 수 있다. 즉, (C//D)*7일 만큼 걸린다.

(2) D를 최대한 채워넣고 남은 나머지 점수는 말 그대로 C를 D로 나눈 나머지인 C%D이다. 여기서부터 생각해보자.

- 보너스점수를 받지 못한다고 생각했을 때 해당 점수를 넘어서기 위해서 필요한 날짜는 며칠일까? 말을 그대로 식으로 바꾼다면, x*A > C%D가 되는 최소 정수 x를 찾으면 된다. 식을 정리하면 x>(C%D)/A를 만족하는 최소 정수 x가 되고, 이를 천장함수를 사용해서 정리하면 x=ceil((C%D)/A)가 된다.

i) 보너스점수를 받으려면 7일은 걸린다. 다르게 말하면, 1일부터 6일까지는 보너스점수를 받지 못하므로 만일 위에서 구한 x가 6이하면 실제 필요한 시간은 딱 x일이다.

ii) 그 외의 경우, 즉 x가 7 이상인 경우를 생각해보자. 위에서는 보너스 점수를 생각하지 않고 x를 구했으므로 x가 7보다 큰 값이 되어도 상관이 없는데, 보너스 점수를 받는다고 하면 상황이 조금 달라진다. 정확히는, C%D점을 얻는 데에 걸리는 날짜에 제약이 걸린다. C%D는 '목표 점수 C를 일주일동안 출첵했을 경우 받을 수 있는 D로 나누고 남은 나머지'이다. 이렇게 얻은 나머지는 아무리 많아봐야 7일 이내에 얻을 수 있는 점수여야 한다. 즉, x가 아무리 크더라도 보너스 점수를 받는 걸 고려하면 7일 이내에 넘어설 수 있는 점수라는 것이다. 즉, 실제 필요한 시간은 min(7, x)일이다.

 

실제 숫자를 넣어서 생각하면 이해가 편하다.

 

매일 출첵에 3점, 보너스 점수 100점, 목표 점수 98점이라고 하자.

D = 7*A+B=7*3+100=121이므로,

(1) 목표 점수 98점까지 D를 한 번도 넣을 수 없다. 여기서 0*7 = 0일 소요.

(2) C%D = 98%121 = 98점이므로, 98점을 보너스 점수 없이 3점씩만 받으면서 넘기고자 한다면 x = ceil(98/3) = 33일이 필요하다. 하지만 날짜가 지남에 따라서 받는 점수를 보면 [3, 3*2, 3*3, 3*4, 3*4, 3*6, 3*7+100]이 되므로, 출첵 6일차 까지는 18점밖에 못 받지만 7일차가 되는 순간 121점이 되어 목표 점수를 곧장 뛰어넘는다. 즉, min(7, 33) = 7일이 필요하다.

 

(2)의 i), ii)를 하나의 식으로 표현하면 깔끔하게도 min(7, x)가 된다! (왜냐하면, i)에서 x가 6 이하인데 이때 min(7, x)==x가 되기 때문) 즉, (1), (2)를 더하여 답을 정리하면 (C//D)*7 + min(7, ceil((C%D)/A))가 된다. 파이썬에는 ceil 함수가 math 모듈 안에 들어있으므로 다음과 같이 코드를 짜면 답이 나온다.

from math import ceil
a,b,c=map(int,input().split())
d=7*a+b
print(c//d*7+min(ceil(c%d/a),7))

매우 짧게 끝나는것 같아 보이는데, 맨 위에 math에서 ceil을 가져오는 것이 숏코딩 하는 것을 막는 것이 보인다. 이를 어떻게 잘 돌아갈 방법이 없을까?

 

ceil함수와 비슷한 역할을 하는 floor 함수를 생각해보자. ceil은 소수점이 있으면 위로 올리는데, floor는 바닥으로 내려주는 역할을 한다. 예를 들어, ceil(3.5)는 4가 되지만, floor(3.5)는 3이 된다. 그리고 파이썬의 // 연산자가 딱 이 floor 연산을 해준다.

그렇다면 이 floor 연산을 딱 우리가 원하는 방향으로 뒤집을 방법은 없을까? 아래의 실험을 보면 힌트를 얻을 수 있다.

print(5//3, 5//-3, -5//3, -5//-3)
# 1 -2 -2 1

계산 결과가 음수가 되면, 그때도 결과보다 작은 최대의 정수로 만들어주므로 사실상 계산 결과를 양수로 부호를 뒤집었을 때 ceil 함수를 씌우고 다시 음의 부호를 붙여주는 것과 같다고 볼 수 있다. 이를 역이용하면, ceil(a/b) 계산 결과값이 -floor(-a/b)와 같고, 이는 -(-a//b)와 같으므로 ceil 함수를 import하지 않아도 같은 기능을 하는 수식을 만들 수 있다.

 

위의 내용을 적용하여 코드를 더 짧게 만들면 다음과 같다.

a,b,c=map(int,input().split())
d=7*a+b
print(c//d*7+min(-(c%d//-a),7))