글 읽기 - 시간초과 어떻게 해결할까요 힌트정도

sibaek 2년 전 0

제가 코드를 작성하면서도 시간 초과나 메모리 초과가 날 만 하다고 느끼기는 하지만 어떻게 해결해야할 지 모르겠습니다. 도움을 주시면 감사하겠습니다.

그래도 최대한 해결하기 위해 음수로 무한정 내려가는 경우나, 세 가지 연산을 했을 때 각각 k * 2값을 초과하는 경우는 k를 찾는 데 무의미하다고 간주하고 사전에 배열에 넣는 것을 방지하도록 했습니다.

{코드 설명}

방식은 arr 리스트(이하 배열)에 n을 넣음으로써 시작되고, n에서 1 빼고, 1 더하고, 2 곱하는 과정을 한 전체 과정마다 존재하는 숫자들만큼 반복하여 k값이 나올 때까지 반복합니다.

만약 n > k 인 경우, 뒤로는 한 칸씩만 움직이는 게 전부이므로 n - k가 답인 것으로 해뒀습니다.

n = k 이면 시간을 쓸 필요가 없으므로 0을 출력합니다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

arr = [n]

time = 0
finish = False
done = False
if n >= k:
    # n은 뒤로 한 칸, 앞으로 한 칸, 앞으로 *2칸 움직일 수 있다.
    # 뒤로는 한 칸씩만 움직일 수 있는게 전부이므로 n - k가 최소 시간이다.
    print(n - k)  
    done = True
while True and not done:  # 동생이 있는 위치에 도달할 때까지 반복
    time += 1
    before = len(arr)
    for i in range(before):
        tp = arr.pop(0)
        if 0 <= tp - 1 <= k * 2:
            arr.append(tp - 1)
        if 0 <= tp + 1 <= k * 2:
            arr.append(tp + 1)
        if 0 <= tp <= k * 2:
            arr.append(tp * 2)
        if k in arr:
            finish = True
            break

    if finish:
        break
    arr = list(set(arr))

if not done:
    print(time)

arr.pop(0)는 arr.pop()과 다르게 o(n)시간 복잡도로 작동합니다. queue 자료형을 사용하실려고 하신것 같은데 그런 경우에는 from collections import deque 하셔서 arr=deque()하시고 arr.popleft()를 사용하시는걸 추천드립니다. list는 stack할때만 사용하시고 deque를 사용하셔야지 pop할때마다 n번씩 도는것을 막을수 있습니다.

sibaek 2년 전 0

deque 사용해서 해봤는데 역시 시간초과입니다.

알고리즘 자체가 비효율적인걸까요? 너비 우선 탐색이라 이게 최선인 거 같은데~

어떻게 해결해야 할 지 잘 모르겠습니다.

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())

arr = deque()

arr.append(n)

time = 0
finish = False
done = False
if n >= k:
    # n은 뒤로 한 칸, 앞으로 한 칸, 앞으로 *2칸 움직일 수 있다.
    # 뒤로는 한 칸씩만 움직일 수 있는게 전부이므로 n - k가 최소 시간이다.
    print(n - k)  
    done = True
while True and not done:  # 동생이 있는 위치에 도달할 때까지 반복
    time += 1
    before = len(arr)
    for i in range(before):
        tp = arr.popleft()
        if 0 <= tp - 1 <= k * 2:
            arr.append(tp - 1)
        if 0 <= tp + 1 <= k * 2:
            arr.append(tp + 1)
        if 0 <= tp <= k * 2:
            arr.append(tp * 2)
        if k in arr:
            finish = True
            break

    if finish:
        break
    arr = deque(set(arr))  # 중복되는 값 제거

if not done:
    print(time)

limepencil 2년 전 2

아 문제를 알았습니다. 코드가 비효율 적이군요. 여기서는 이미 방문한곳을 저장해놓고 있지 않기 때문에 한번 돌때마다 적어도 방문하는 곳이 3배씩 증가합니다. 이런식으로 가면 20번만 해도 3486784401방법들이 나올수 있습니다. 차라리 distance = [0]*(100001)에 거리마다 최단 숫자를 저장해서 bfs의 필수인 visited를 구현하여 반복되게 똑같은 곳을 방문을 안하는것이 좋아 보입니다.

sibaek 2년 전 0

distance = [0]*(100001)에 거리마다 최단 숫자를 저장한다고 하셨는데

최단 숫자라는게 이해가 잘 안됩니다. 설명해 주시면 감사하겠습니다.

limepencil 2년 전 0

이제 예를 들어서 3초만에 943이라는 위치에 처음 방문했으면 distance[943]=3 를 저장함으로서 나중에 이 위치에 오게 되면 이미 더 빠르게 도착할수있는걸 알기 때문에 멈춰줄수 있습니다. 이런식으로 저장해주면 최악의 상황에도 100001번만 돌면 되기 때문에 훨씬 빨리 풀수 있습니다.

sibaek 2년 전 1

이해하고 잘 해결했습니다~

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 어떻게 해결할까요 힌트정도

sibaek 2년 전 0

limepencil 2년 전 0

sibaek 2년 전 0

limepencil 2년 전 2

sibaek 2년 전 0

limepencil 2년 전 0

sibaek 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말