백준 달팽이는 올라가고 싶다/에라토스테네스의 체

2023.01.03. 복습 결과 => 스스로 풀지 못함

 

 

a, b, v = list(map(int, input().split()))
h = 0
day = 0
while h<v:
    day += 1
    print(day)
    h = h + a
    if h >= v:  # 목표 높이 이상 올라간 경우
        break
    h = h - b

print(day)

위 문제를 그대로 구현한 코드이다. 당연히 로직은 맞지만, 계산이 오래걸리는 경우에 시간 초과가 나온다.

따라서 다른 로직으로 작성해야한다.

 

 

내 코드)

split을 사용하여 세 정수를 한 줄에 나눠서 입력받는다.

만약, a==v이면 낮에 올라가는 것만으로도 도착할 수 있으므로 하루가 걸린다. 

a<v이면 직접 로직을 작성하여 며칠이 걸리는지 계산해줘야한다. 

 

하루에 a-b만큼씩 이동을 하므로 이것을 변수 d에 넣어둔다.

그럼 .단순히 v를 d로 나누면 원하는 결과를 얻을 수 있을까? => 아니다.

만약, a가 충분히 크고 b가 매우 작을 경우에는 원하지 않는 결과가 나온다 ex) 100 99 1000000000

 

달팽이가 올라가기 시작한다는건 반드시 낮 동안에는 나무 막대로 올라가므로

남은 거리 left= 막대길이- 낮 동안 가는 거리를 d(하루에 이동하는 거리)로 나눠야 한다.

 

만약 나눈 결과가 딱 나누어 떨어진다면 몫(걸리는 날짜)+1(낮 동안 간 거리를 뺀 상태를 나눈 것이므로 하루를 더 더해줌)

 

만약 나눈 결과가 나누어 떨어지지 않는다면, 몫을 구해주는 과정에서 소수점이 드랍이 되므로 날짜를 하나 더 더해준다

(0.xxxx도 하루니까)

그 다음, 위와 마찬가지로 이미 낮 동안 간 거리를 빼준 상태에서 연산을 한 것이므로 최종 결과에 1을 더해준다.

 

복습하면서 더 클린하게 작성하였다. 로직은 위와 동일하다.

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

diff = a-b  # 하루에 올라갈 수 있는 높이
left = v - a  # 이동할 거리 => 달팽이는 반드시 올라가야하므로 목표 높이에서 낮에 올라가는 거리를 빼줌 ==> 마지막 결과에 1을 더해줘야함

check = left % diff  # 이동할 거리를 하루 이동거리로 나누어 떨어지는지 확인 필요
day = left//diff

if check == 0:  # 만약 나누어 떨어지면
    print(day+1)  # 낮에 올라간 거리를 빼준 상태에서 구한 결과인데, 낮도 하루이므로 1을 더해줘야함
else:  # 나누어 떨어지지 않을 경우
    print(day+2)  # day를 구하는 과정에서 소수점이 떨어져 나가는데, 그 소수점도 하나의 날짜이므로 그것까지 포함하여 2를 더해줘야함

 

 

 

def sosu(n):
    if n == 1:
        return 1
    else:
        for i in range(2, int(n ** 0.5) + 1):  # 에라토스테네스의 체
            if n % i == 0:
                return 1
        return 0


m, n = list(map(int, input().split()))

for i in range(m, n + 1):
    if sosu(i) == 0:
        print(i)

이 문제는 간단하게 소수 구하는 문제인데, 답은 제대로 나오지만 큰 숫자가 들어가면 시간초과가 난다.

=> 에라토스테네스의 체를 사용해야된다.

에라토스테네스의 체란, 소수임을 판별하기 위해 모든 범위에서 나누기 하는 것이 아니라,

해당 숫자의 제곱근까지만 보면 소수임을 판별할 수 있다는 로직이다.

5행을 보면, 에라토스테네스의 체를 사용해 제곱근을 직접 구하여 범위를 줄여 시간을 단축시켰다.