오늘의 한 마디
알고리즘 자체를 몰라서 못 푸는 문제가 아닌 이상,
이 문제 풀었던 것처럼 섣불리 답을 보지 말고 끈기있게 틀려가며 고민해보자!
- Baekjoon 문제 링크
- solved.ac > 문제 > CLASS 4에 수록된 문제입니다.
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.
예제 입력 1
5 17예제 출력 1
4
2발상
Try #1 : 메모리 초과
그냥 bfs 최단 거리인줄 알았지만, 이번에는 방법의 수를 추가로 출력해야 한다.
import sys
N, K = map(int, sys.stdin.readline().rstrip().split())
time = 0
q = [N]
while q:
q_cpy = q[:]
q = []
cnt = 0
for case in q_cpy:
if case == K:
cnt += 1
q.append(case-1)
q.append(case+1)
q.append(case*2)
if cnt:
print(time)
print(cnt)
exit()
time += 1메모리 초과
case-1, case+1, case*2가 0<=x<=100000 경계를 넘어서는 경우는 굳이 고려할 필요가 없다!
Try #2 : 메모리 초과
import sys
N, K = map(int, sys.stdin.readline().rstrip().split())
time = 0
q = [N]
while q:
q_cpy = q[:]
q = []
cnt = 0
for case in q_cpy:
if case == K:
cnt += 1
if 0 <= case-1 <= 100000:
q.append(case-1)
if 0 <= case+1 <= 100000:
q.append(case+1)
if 0 <= case*2 <= 100000:
q.append(case*2)
if cnt:
print(time)
print(cnt)
exit()
time += 1메모리 초과
메모리가 어디서 초과되는지 알아보았더니,
visited를 따로 사용하지 않기 때문에 중복 제거를 할 수 없었고,
q의 크기가 time이 1 증가할 때 3배씩 계속 늘어난다는 것을 알아내었다.
Try #3 : 시간 초과
import sys
N, K = map(int, sys.stdin.readline().rstrip().split())
time = 0
visited = [0] * 100001
visited[N] += 1
while True:
visited_cpy = visited[:]
visited = [0] * 100001
for i in range(len(visited_cpy)):
if visited_cpy[i] and i == K:
print(time)
print(visited_cpy[i])
exit()
if visited_cpy[i]:
if 0 <= i-1 <= 100000:
visited[i-1] += 1
if 0 <= i+1 <= 100000:
visited[i+1] += 1
if 0 <= i*2 <= 100000:
visited[i*2] += 1
time += 1시간 초과
갔던 곳을 이후 time에서 또 방문하는 경우, 이건 이미 글러먹은 케이스기 때문에 굳이 생각하지 않아도 되지 않은가?
Try #4 : 시간 초과
import sys
INF = int(1e9)
N, K = map(int, sys.stdin.readline().rstrip().split())
time = 0
visited = [0] * 100001
distance = [INF] * 100001
visited[N] += 1
distance[N] = 0
while True:
visited_cpy = visited[:]
visited = [0] * 100001
for i in range(len(visited_cpy)):
if visited_cpy[i] and i == K:
print(time)
print(visited_cpy[i])
exit()
if visited_cpy[i]:
if 0 <= i-1 <= 100000 and time <= distance[i-1]:
visited[i-1] += 1
distance[i-1] = time+1
if 0 <= i+1 <= 100000 and time <= distance[i+1]:
visited[i+1] += 1
distance[i+1] = time+1
if 0 <= i*2 <= 100000 and time <= distance[i*2]:
visited[i*2] += 1
distance[i*2] = time+1
time += 1distance 리스트를 따로 만들어서 이 인덱스(지점)까지 도달하는데 걸리는 최단 time을 저장해보았다.
시간 초과
혹시 100000개를 매 time마다 탐색하게 하는데서 시간이 걸리나? queue랑 섞어볼까?
풀이 : 148ms
드디어 맞았다!
시간 148ms로 매우 빨라서 더더욱 뿌듯하다.
import sys
INF = int(1e9)
N, K = map(int, sys.stdin.readline().rstrip().split())
time = 0
visited = [0] * 100001
distance = [INF] * 100001
visited[N] += 1
distance[N] = 0
q = [N]
while q:
q_cpy = q[:]
q = []
if visited[K]:
print(distance[K])
print(visited[K])
exit()
for n in q_cpy:
if 0 <= n-1 <= 100000 and time < distance[n-1]:
if not visited[n-1]:
q.append(n-1)
visited[n-1] += visited[n]
distance[n-1] = time+1
if 0 <= n+1 <= 100000 and time < distance[n+1]:
if not visited[n+1]:
q.append(n+1)
visited[n+1] += visited[n]
distance[n+1] = time+1
if 0 <= n*2 <= 100000 and time < distance[n*2]:
if not visited[n*2]:
q.append(n*2)
visited[n*2] += visited[n]
distance[n*2] = time+1
time += 1겹치는 부분을 제거하여 이렇게 개선할 수도 있겠다.
import sys
INF = int(1e9)
N, K = map(int, sys.stdin.readline().rstrip().split())
time = 0
visited = [0] * 100001 # 여기로 몇번 왔는지 저장
visited[N] = 1
distance = [INF] * 100001 # 최단횟수 저장
distance[N] = 0
q = [N]
while q:
q_cpy = q[:]
q = []
if visited[K]:
print(distance[K])
print(visited[K])
exit()
for n in q_cpy:
for next_n in [n-1, n+1, n*2]:
if 0 <= next_n <= 100000 and time < distance[next_n]:
if not visited[next_n]:
q.append(next_n)
visited[next_n] += visited[n]
distance[next_n] = time+1
time += 1