백준 2869번 풀이

문제

달팽이가 하루동안 올라가는 거리와 자다가 미끄러지는 거리가 주어질 때, 일정 거리의 막대기를 올라가려면 며칠이나 걸리는지 출력하라.

Reference

https://www.acmicpc.net/board/view/79818 (해당 문제의 질문글)

풀이

야 근데 100 99 1000000000은 너무했다… 이건 올라가다 달팽이 죽어요… 물론 관찰자도 죽는다 이정도면 햇수로 환산해도 아득한 세월이다… 

import sys
climb,omg,bar = map(int,sys.stdin.readline().split())
print(climb,omg,bar)

climb: 올라간 높이

omg: 자다가 미끄러진 높이(OMG=oh my god) 달팽이가 일어나자마자 미끄러진 거 보고 오 마이 갓 하는거지

bar: 막대기

아니 변수로 빵터뜨리기 있냐고 저기에 day라는 변수가 추가되는데 day는 말 그대로 올라가는 데 걸리는 시간, 즉 최종 산물이다. 그러면 달팽이가 올라가는거 내려가는거 더하고 빼고 하다가 정상에 다다르면 그만하면 되니까 while 주면 되겠네?

import sys
climb,omg,bar = map(int,sys.stdin.readline().split())
# omg = Oh My God의 약자. 보통 OMG로 쓰는데 귀찮아서 소문자로 썼습니다. 
# 자는동안 미끄러진 달팽이가 다음날 일어나서 OMG 하는거죠 뭘... 
day = 0

while bar > 0:
    day += 1
    bar -= climb
    if bar == 0: 
        break
    else:
        bar += omg
print(day)

님 이거 생각하셨음? 나도 그랬는데 시간초과 떠요 저거. 시간제한 0.15초임.

참고문헌에 가면 정답 코드가 있는데… 나도 사실 저게 왜 저렇게 됐는지는 잘 모른다. 근데 일단 내가 이해한거는 설명드림.

저걸 막대기 시점에서 보면 달팽이가 올라간 만큼 남은 길이가 줄어들고, 미끄러진 만큼 남은 길이가 올라간다. 그러니까 달팽이가 다 올라갈때까지 올라간 만큼 빼고 미끄러지는 만큼 더하고를 반복하다가 마지막 날에 올라간 만큼을 뺀다. (그러면 남은 거리가 0이 된다) 그러니까 최종적으로 막대기의 길이+미끄러지는 만큼(곱하기 일수-1)=달팽이가 올라가는 높이(곱하기 일수)가 된다.

import sys
climb,omg,bar = map(int,sys.stdin.readline().split())
# omg = Oh My God의 약자. 보통 OMG로 쓰는데 귀찮아서 소문자로 썼습니다. 
# 자는동안 미끄러진 달팽이가 다음날 일어나서 OMG 하는거죠 뭘... 
day = (bar - omg) / (climb - omg)
print(day)

그럼 이대로 내면 되나요? 아뇨 소수점 떠서 안됩니다.

import sys
climb,omg,bar = map(int,sys.stdin.readline().split())
# omg = Oh My God의 약자. 보통 OMG로 쓰는데 귀찮아서 소문자로 썼습니다. 
# 자는동안 미끄러진 달팽이가 다음날 일어나서 OMG 하는거죠 뭘... 
day = (bar - omg) // (climb - omg)
print(day)

그럼 이거요? 아뇨 그러면 소수점 싹 버려버리는데요?

import sys
import math
climb,omg,bar = map(int,sys.stdin.readline().split())
# omg = Oh My God의 약자. 보통 OMG로 쓰는데 귀찮아서 소문자로 썼습니다. 
# 자는동안 미끄러진 달팽이가 다음날 일어나서 OMG 하는거죠 뭘... 
day = (bar - omg - 1) // (climb - omg) + 1
print(day)

이게 정답인데… 아 math 안지움… 아무튼 저기에 1이 붙은 이유가 뭔가가 참고문헌에 있는 글 내용이었고 답변은 “ceil(p/q) = floor((p+q-1)/q)”를 보면 이해가 될 거라는 말이었다. 뭔 소리여… 싶어서 직접 해봤더니 값이 같네.

print(math.ceil(omg/climb),math.floor((omg+climb-1)/climb))

둘이 같다. ceil은 가장 가까운 정수로 올림하는거고, floor는 가장 가까운 정수로 내림하는 것. 각각 계산 결과가 1/5, (1+5-1)/5. 전자는 0.2지만 올림하니까 1이고 후자는 그냥 1이다. 그런데 이거 math 불러서 해결보자니 시간초과 날 것 같단말이지… 그리고 //가 사실상 floor랑 비슷하니까(몫만 보여준다) -1을 도입한 듯.

저기에 예시로 준 5, 1, 6을 대입해서 풀면 +1이 없을 때 (6-1-1) // (5-1)해서 1이 나오게 되는데, 실제로 정답은 2다. 저 +1이 분모에 붙어있는 게 아니라 따로 떨어져 있는 애다. (분모에 붙어있으면 괄호로 묶는다)