백준 2869 - 파이썬

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

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

이 문제는 일반적이 반복문으로 풀이하면 시간 초과가 나는 문제이다. 역시나 처음에 반복문으로 금방 풀어서 제출했는데 시간 초과가 났다. 그래서 반복문으로 접근하는 것이 아닌 수식으로 접근해서 풀어야 하는 문제인거 같아서 문제 풀이 공식을 찾고자 했다. 난이도가 브론즈1로 되어있길래 금방 생각날 줄 알았는데 2%가 부족하게 답이 안 나왔다. (나머지로 구해야 할거 같은데 여기서 더 나아가질 않음..) 한 30분정도 고민하다가 다른 사람들이 풀이를 정리해둔 블로그를 참고했다.

 

해당 블로그에서는 나무막대에 도착하는 날을 x라고 하고, 미끄러지는 날을 x-1로 정의하고 시작했다. x는 A번을 반복한 것이기에 서로 곱하고, x-1은 B번 반복한 것이기 때문에 둘을 곱한 후 더하면 나무막대 v에 도달할 수 있다. 이를 식으로 나타내면 V = Ax + B(x-1)가 되고, 이를 x로 정리하면 x = (V - B) / (A - B)가 된다. 이제 구해낸 공식을 코드로 옮기면 끝이다.

 

코드

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

if (v - b) % (a - b) == 0:
    print((v-b) // (a-b))
else:
    print((v-b)//(a-b) + 1)

 

나머지가 0일 때는 나무 막대에 부족한 거리 없이 도달한 것이고, 나머지가 0이 아닐 때는 도달하기 살짝 부족한 것이기에 하루 더 추가하는 의미로 1을 더해준다.

 

import math

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

day = (v-b) / (a-b)
print(math.ceil(day))

 

두번째 코드는 ceil함수를 써서 실수를 올림하여 출력한 것이다.

 

느낀점

이번 문제를 풀면서 브론즈라고 쉽게 생각하면 안되겠다고 생각했고, 이런 문제 유형들은 아직 부족하다는 점을 느꼈다. 아직 취준까지 시간은 많이 남았고, 사실 지금도 군대에서 휴가 나와서 풀고 있는 것이니 조급해 하지 말고 간단한 문제들부터 복잡한 문제들까지 차근차근 풀어나가야 되겠다.