글 읽기 - Python 83% 틀렸습니다. - 오답 부분이나 반례 부탁드립니다. ㅜㅜ

tlaxh000 2년 전 0

질문 내 반례들 모두 올바르게 나오는거 같은데 82~83% 쯤 오답으로 처리가 되네요.

제가 생각한 방법은 배주 항등식을 이용해서 도달이 불가능한 경우 탐색을 진행하지 않고 바로 출력하도록 하고,

도달 가능할때만 탐색 진행했습니다.

어떤 부분이 잘못됐는지 고수님들의 조언 부탁드립니다. ㅜㅜ

from collections import deque
F, S, G, U, D = map(int, input().split())

def GCD(a, b):
    if b == 0: return a
    return GCD(b, a%b)

def Search():
    queue = deque()
    queue.append(S)
    visited = [-1] * (F+1)
    visited[S] = 0

    while queue:
        cur = queue.popleft()
        if cur == G:
            return visited[cur]
        
        for pos in [U, (-1*D)]:
            next_floor = cur + pos
            if (next_floor>= 1) and (next_floor <= F) and visited[next_floor] == -1:
                visited[next_floor] = visited[cur] + 1
                queue.append(next_floor)

if (D == 0 and (G-S) < 0) or (U == 0 and (G-S) > 0): ## U이나 D 이 없으면 올라가야하는 경우나 내려가야하는 경우가 불가능하다.
    print('use the stairs')
else:
    ## 배주 항등식을 이용하여 탐색을 거치지 않더라도 불가능한 경우 미리 판단하도록 한다.
    """
    Ux + Dy = GCD(U, D)*k (k는 정수)
    즉 U, D의 최대공약수의 배수로 표현 가능하면 탐색하도록 한다.
    """
    if abs(G-S) % GCD(max(U,D), min(U,D)) == 0:
        print(Search())
    else: ## 최대공약수의 배수로 표현이 불가능하면 도달 불가능.
        print('use the stairs')

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

문제

문제

출처

ICPC

Python 83% 틀렸습니다. - 오답 부분이나 반례 부탁드립니다. ㅜㅜ

tlaxh000 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말