https://www.acmicpc.net/problem/17071
공부 날짜 : 2023.02.08
정답 참조 여부 : △
수빈이는 매초 +1 or -1 or *2의 위치로 움직일 수 있다.
동생은 매초 가속을 하며 움직이며 k를 시작으로 1초 후 k+1 2초 후 k+1+2 3초 후 k+1+2+3의 위치로 움직일 때 수빈이와 동생이 만나는 최단시간을 구하는 문제이다.
코드가 어렵기보단, 문제를 푸는 아이디어가 어려웠다.
가장먼저 푼 방법은 50만개의 칸에 BFS를 통해 최단경로를 탐색한 뒤에 시간을 0~1000초동안 동생의 위치를 갱신하며 해당 위치에 수빈이가 도착한 시간을 체크 했다.
해당 방식의 문제는 예제부터 틀렸는데
17 5
# -> 4
# 동생 5 > 6 > 8 > 11 > 15
# 수빈 17 > 16 > 15 > 14 > 15
가 되어 틀리게 된다.
즉, 최단경로를 찾는게 아니였던 것이다.
그래서 혹시나 하고 그냥 모든경우를 탐색을 했는데 결과는 당연히 시간초과 시간 복잡도가 무려 O(3^1000)이 나온다.
그래서 다음으로 생각한 방법은 수빈이가 특정위치에 도착하게되면 그 이후로는 2초 간격으로 해당위치에 왔다갔다 하면서 동생을 기다릴 수 있는 것이였다.
그래서 마찬가지로 BFS로 최단경로 탐색 후 0~1000초 동안 동생의 위치를 살펴보는데, 동생이 도착한 위치에 수빈이가 먼저 도착했고, 그 차이가 2의 배수이면 그 때의 시간을 출력했다.
결과는 탈락 역시 플레문제라 쉽지가 않았다.
마지막 방법은 현재 내 SSAFY 담당 교수님께서 조언을 해주셨다.
바로 홀, 짝을 모두 탐색하는 것
현재 내 방법은 단지 최단경로만 탐색했다. 그렇기 때문에 동생이 특정 위치에 도착 했을 때 수빈이와 동생이 해당위치에 도착하는 시간이 모두 홀수 or 짝수여야만 한다.
그렇기 때문에 탐색 과정에서 홀수의 최단경로, 짝수의 최단경로를 모두 탐색해서 구해줬고,
그 다음 동생이 도착했을 때 홀수면 홀수경로보다 크고 짝수면 짝수경로보다 크고, 같은 홀,짝일때 시간을 출력하도록 했더니 정답으로 나왔다!
홀수와 짝수를 나눈다는 생각을 스스로 할 수 있었을지 모르겠다.
문제를 풀어가는 과정이 정답에 가깝게 흘러갔고 마지막 열쇠는 도움을 받아 결국 정답으로 나왔다.
플레는 정말 어렵다고 생각했는데 결국 문제를 풀어서 정말 기분이 좋았고 아직 성장 할 수 있다는 생각을 가질 수 있는 문제 였다.
소스코드
# 임의의 칸에 짝수번째로 도착하는 경우
# 임의의 칸에 홀수번째로 도착하는 경우
# 2가지 모두 가능할 수도 있다.
# 고르 2가지 경우가 모두 해당한다면 해당 시간 이후로 도착하는 모든 동생과 만날 수 있다.
import sys
from collections import deque
input = sys.stdin.readline
############################################
n, k = map(int, input().split())
visited = [[-1 for _ in range(500001)]for _ in range(2)]
visited[0][n] = 0
visited[1][n] = -1
visit = deque()
visit.append((n, 0,))
# 모든칸에 최소횟수로 도달
while visit:
x, dis = visit.popleft()
# 현재 장소에서 이동가능하고, 이전에 방문하지 않은 모든 칸 추가
if 0 <= x+1 <= 500000 and visited[(dis+1) % 2][x+1] == -1:
visited[(dis+1) % 2][x+1] = dis + 1
visit.append((x+1, dis+1))
if 0 <= x-1 <= 500000 and visited[(dis+1) % 2][x-1] == -1:
visited[(dis+1) % 2][x - 1] = dis + 1
visit.append((x-1, dis+1))
if 0 <= x*2 <= 500000 and visited[(dis+1) % 2][x*2] == -1:
visited[(dis+1) % 2][x * 2] = dis + 1
visit.append((x*2, dis+1))
# print(visited[0][500000], visited[1][500000])
for i in range(1001):
position = k + ((i**2 + i) // 2)
if position > 500000:
print(-1)
break
answer = 1001
if i - visited[0][position] >= 0 and (i - visited[0][position]) % 2 == 0:
print(i)
break
if i - visited[1][position] >= 0 and (i - visited[1][position]) % 2 == 0:
print(i)
break
