FilesExpand file tree

 master

/

backjun_1697.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (41 loc) · 1.61 KB

 master

/

backjun_1697.py

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (41 loc) · 1.61 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

'''수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에

있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.

순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.'''

class Queue(object):

def __init__(self):

self.items = []

def put(self, N):

self.items.insert(0, N)

def get(self):

return self.items.pop()

q = Queue()

def location(N, K):

q.put(N)

visited = [False for i in range(100000)]

visited[N] = True

if N > 100000 or K > 100000:

return

count = 0

route = {i: 0 for i in range(10000)}

while True:

N = q.get()

count += 1

if N == K:

return route[N], N, K

if N + 1 < 100000 and visited[N + 1] == False:

q.put(N + 1)

visited[N + 1] = True

route[N + 1] = route[N] + 1

if N - 1 > 0 and visited[N - 1] == False:

q.put(N - 1)

visited[N - 1] = True

route[N - 1] = route[N] + 1

if 2 * N < 100000 and visited[2 * N] == False:

q.put(2 * N)

visited[2 * N] = True

route[2 * N] = route[N] + 1

numbers = input()

K, N = numbers.split(' ')

N, _, _ = location(int(K), int(N))

print(N)