글 읽기 - 반례 찾아주실수 있으실까요..

won7963 3년 전 0

N과 K는 항상 K가 큰 값을 가지도록 정리 한 다음,

0~(K+(K/2)+1) 의 크기를 갖는 공간 안에서 1초가 지날때 마다 갈 수 있는 지점에 해당 시간을 표기하는 식으로 풀이했습니다.

아래 써놓은 경우의 수는 모두 정답을 출력하는데 어떤부분에서 걸리는지 잘 모르겠어요.

N 과 K 가 같을떄, N = 999 K = 1000일 떄도 잘 작동합니다.

TEST CASE #1:
6 16
exp -> 3
you -> 6

TEST CASE #2:
8 20
exp -> 3
you -> 5

TEST CASE #3:
15964 89498
exp -> 4781
you -> 19110

3 43
출력: 7
정답: 6
3 -> 6 -> 12 -> 11 -> 22 -> 44 -> 43

4 27
출력: 6
정답: 5
4 -> 8 -> 7 -> 14 -> 28 -> 27

5 35
출력: 6
정답: 5
5 -> 10 -> 9 -> 18 -> 36 -> 35

6 43
출력: 6
정답: 5
6 -> 12 -> 11 -> 22 -> 44 -> 43

7 43
출력: 7
정답: 6
7 -> 6 -> 12 -> 11 -> 22 -> 44 -> 4

from sys import stdin
from collections import deque


def sol():
    N, K = map(int, stdin.readline().split())

    if N > K:
        temp = K
        K = N
        N = temp

    halfK = K // 2 + 1

    if N == K:
        print(0)
        return
    space = [0 for i in range(1, K + halfK + 1)]
    que = deque([[N]])
    #print(que)
    times = 0
    while True:
        times += 1
        current = que.pop()
        #print(current)
        travable = []
        for node in current:
            if node - 1 == K or node + 1 == K or node * 2 == K:
                print(times)
                return
            if node - 1 > 0:
                if space[node - 2] == 0 or space[node - 2] > times:
                    space[node - 2] = times
                    travable.append(node - 1)
            if node + 1 <= K + halfK:
                if space[node] == 0 or space[node] > times:
                    space[node] = times
                    travable.append(node + 1)
            if node * 2 <= K + halfK:
                if space[(node * 2) - 1] == 0 or space[(node * 2) - 1] > times:
                    space[(node * 2) - 1] = times
                    travable.append(node * 2)
        que.append(travable)


sol()

yj10516 3년 전 1

input

100 0

ans : 100

return: 9

won7963 3년 전 1

감사합니다!

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

문제

문제

출처

ICPC

반례 찾아주실수 있으실까요..

won7963 3년 전 0

yj10516 3년 전 1

won7963 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말