[백준] 2869 python(파이썬) : 달팽이는 올라가고 싶다 - 상세해설

https://www.acmicpc.net/problem/2869

2869번: 달팽이는 올라가고 싶다

 

 

 

시간제한이 없다면 반복문으로 해결할 수 있는 문제입니다.

 

a, b, v = map(int, input().split())
x, y = 0, 0

def func(a, b, v):
    global x, y
    while True:
        y += 1
        x += a
        if x >= v:
            return y
        else:
            x -= b
print(func(a, b, v))

 

시간제한이 1초였다면 정답률이 이렇게 낮지도 않았을 거라 생각합니다.

 

하지만, 0.15초 안에 풀어야 하는 문제이기에 반복문을 사용하면 시간 초과에 걸리게 됩니다.

 

이런 유형의 촉박한 시간제한을 두는 문제는 공식을 만들어서 해결해야 하는 경우가 많은데, 이 문제도 그렇다고 생각합니다.

 

아이디어

구하려고 하는 것은 결국 며칠이 걸렸는가? 즉, 날짜를 구하는 것

날짜는 총 거리 / 움직이는 거리

문제에서 a, b, v로 변수를 지정했으니 하루 동안 움직이는 거리는 (a - b)가 됩니다.

 

그리고 낮에 올라가는 거리 a, 밤에 미끄러지는 거리 b이지만, 마지막 날 낮에 올라가서 목표 지점에 도달하면 그 다음은 미끄러지지 않으므로 b를 빼줄 필요가 없습니다.

 

day = v / (a - b)라고 하면 원하는 값에서 1씩 값이 크게 나옵니다. 즉, 정상에 올랐어도 다음날 다시 오른다는 뜻이죠.

그래서 높이에 대해서 정리를 하면  v = day * (a - b) + a가 됩니다. a만큼 올랐다 b만큼 떨어지기를 반복하고 마지막날 a만큼 오르면 더는 떨어지지 않기 때문입니다.

 

정리하면 day = (v - a) / (a - b)

 

*총 높이(v)에서 마지막날 오른 a를 빼고 (a - b)를 나누면 a 만큼 올라간 마지막 날을 제외한 날짜를 구할 수 있습니다.

 

마지막 날이 빠졌으니 식에서 +1을 해주면 최종 공식이 완성됩니다.

 

day = (v - a) / (a - b) + 1

 

*하지만, 경우에 따라 결괏값이 정수로 나오지 않고 실수로 나오는 경우가 발생합니다.

 

예제 입력 2 같은 경우입니다.

 

5 1 6

 

결괏값은 1.XXXX가 나오게 됩니다. 

 

1.XXX일이 나오는 경우 날짜는 정수이므로 2일이 필요합니다.

 

그래서 그것을 위한 보정 작업이 필요합니다.

 

코드는 다음과 같습니다.

 

a, b, v = map(int, input().split())
day = (v - a) / (a - b) + 1
print(int(day) if day == int(day) else int(day)+1)

 

마지막 print는 삼항 연산자를 활용했습니다.

 

의미는 4.2일이 나왔을 경우 5일이 필요하니 4.2일의 정수형으로 바꾸고 +1을 해준 값을 출력한다는 의미입니다.

 

삼항 연산자에 관한 글은 링크를 접속해 주세요.

 

https://hgk5722.tistory.com/39

[Python] 파이썬의 삼항연산자

 

아이디어2

 

이번엔 아이디어 1과 비슷한 방식으로 구글에 해답을 검색하면 가장 잘 나오는 "day = (v-b-1) / (a - b) + 1"이 어떻게 나오는지 설명해 보겠습니다.

 

그전에 day = (v-b) / (a - b)로 하면 안되는 이유는 원하는 출력값에서 +1 되는 값이 출력되어서 그렇습니다.

 

 

 

그럼 그림으로 설명해보겠습니다.

 

그림 속 탑은 달팽이가 가야하는 총 거리(v)를의미 합니다.

빨강색 물결 표시는 우리가 원하는 마지막 날 멈추는 구간입니다. 아침까지의 이동거리이지요. v = day(a - b) + b로 총 높이를 설정해서 day로 풀어주면 day = (v - b) / (a - b) 가 나오게 됩니다. 하지만, 여기서 멈추면 출력에서 오류가 나게 되므로 공식을 수정해 줍니다. 초록색 표기 부분은 총 거리에서 -1을 해서 하루치 이동을 뺀 것입니다. 그것을 (a - b)로 나누면 도착 하루전까지의 날짜를 구할 수 있습니다. 그리고 +1을 해주면 보라색 표기 부분이 되며 우리가 원하는 빨강색 물결 표시에 도착할 수 있게 됩니다.