[개강 준비 과정 - 선택 트랙] 알고리즘 스터디 2일차

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

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

계속 붙잡고 있다 보니 위 문제를 결국 풀게 되었다.

 

시간제한이 0.25초라고 나오는데

구글에 검색을 해보면 대략 O(N)의 시간 복잡도를 가질 때 1초의 시간 동안 최대 약 1억 개의 입력이 가능하다고 한다.

(참고 : https://lemonlemon.tistory.com/54)

Big O notation 과 시간 제한 (보통 1초 제한이라고 하면 어느정도?)

 

그럼 0.25초 동안은 약 4억개의 입력이 가능한데 (제대로 이해한건지..?)

2869번은 입력 범위가 (1 ≤ B < A ≤ V ≤ 1,000,000,000) 로 최대 10억까지 가능하니 O(N)의 복잡도로는 문제를 해결하지 못한다.

 

O(1)의 시간 복잡도를 이용해야 하므로

while 문을 지우고 한참을 생각하고 시도해 본 결과 문제를 맞힐 수 있었다.

 

# 수정 전
def goUp(up, down, height):
    day = 1
    while (up*day - down*(day-1) < height):
        day += 1
    print(day)

A, B, C = map(int, input().split())
goUp(A, B, C)

# 수정 후
import math
def goUp(up, down, height):
    speed = up - down
    day = ((height - up)/speed)
    print(math.ceil(day)+1)

A, B, C = map(int, input().split())
goUp(A, B, C)

 

이 문제를 풀면서 무턱대고 문제를 푸는 것이 중요한 게 아니라 우선 전반적인 알고리즘의 개념을 배우는 것이 먼저인 것 같아 제공받은 강의를 듣기 시작하였다.

 

실제 2일 차는 25일 날 진행하였고 이 글을 작성하는 날짜는 7/31인데

강의에 나오는 문제들을 거의 하루종일 잡고 있다 보니 글 쓸 시간이 없었다...