인프런 커뮤니티 질문&답변
작성한 질문수
안녕하세요. 3 - I 질문 있습니다.
작성
·
423
0
안녕하세요 큰돌 선생님.
늘 양질의 강의 감사드리며, 제 코드에 어느 부분이 도대체 문제가 되어 틀렸다고 하는지 찾아낼 수 없어
다시 한번 질문 올리게 되었습니다.
저는 동생의 위치를 1부터 n까지의 합 공식을 이용하여 별도의 queue에 저장했고,
수빈이가 움직일 수 있는 3가지 경우마다 push, pop을 이용해
수빈이의 위치와 동생의 위치가 같은지 체크했습니다.
그리고 다음 숫자(next)가 이미 방문했던 숫자여도 현재 동생의 위치와 같다면
바로 그 당시의 위치를 출력하도록 처리했습니다.
나름 예외처리를 위해 신경썼는데, 고민하다가 결국 갈피를 못 잡았습니다.
답변 기다리고 있겠습니다. 항상 감사합니다.
답변 1
0
안녕하세요 잼코님 ㅎㅎ
저는 동생의 위치를 1부터 n까지의 합 공식을 이용하여 별도의 queue에 저장했고,
수빈이가 움직일 수 있는 3가지 경우마다 push, pop을 이용해
수빈이의 위치와 동생의 위치가 같은지 체크했습니다.
>> 이부분은 정말 잘 짜셨습니다.
그리고 다음 숫자(next)가 이미 방문했던 숫자여도 현재 동생의 위치와 같다면
바로 그 당시의 위치를 출력하도록 처리했습니다.
>> 이부분은 이 코드 말씀하시는 거겠죠?
if (visited[next] && next == next_dest) {
cout << before << "\n";
return 0;
}근데 제가 반례를 들어볼게요.
자, 3이라는 지점에 동생이 5초에 도착합니다. 근데 수빈이가 3이라는 지점에 "이미" 4초에 도착했어요. 근데 이거를 기반으로 해당 초를 출력하고 이 코드를 종료시키는게 맞을까요? 수빈이가 4초에 도착했다면 6, 8, 10초에 그 지점에 도착할 수 있다는 것이 됩니다. 왜냐하면 수빈이는 +1, -1이 되기 때문에 왔다리 갔다리 하면서 해당 지점을 방문할 수 있는 것이죠. 즉, 5초에는 방문이 불가능한 것이죠.
이러한 반례 때문에 홀 짝을 나눠서 코드를 구축해주셔야 합니다. 다음코드 처럼 말이죠.
int visited[2][max_n + 4]
감사합니다.