3-I 질문 있습니다

인프런 커뮤니티 질문&답변

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-I

작성

376

수정됨

이 코드가 틀린 코드인거 압니다.

근데 이 코드에 테스트 케이스 5,17을 입력했을때 벡터의 범위를 벗어난다고 하더군요.

5,17의 경우 K가 20일때 visited[20]이 3이되면서 50만을 전혀 무리없이 넘기지 않고 일찍 종료되는데, 대체 왜 범위를 벗어난다는건지 모르겠네요.

테스트케이스 250000, 499999을 입력하면 잘 돌아갑니다.

그리고 이 문제에서 홀짝을 굳이 생각해야하나요? 기존 숨바꼭질 문제의 bfs로직에서 동생의 위치만 실시간으로 변하는걸 고려해서 짜면 되는거 아닌가요?

답변 1

지식공유자

안녕하세요 ㅎㅎ

홀짝을 왜 생각해야 할까요?

예를 들어 수빈이가 3 지점에 5초에 왔습니다. 동생은 7초에 왔구요. 그러면 수빈이와 동생은 만날 수 있을까요?

만날 수 있죠. 3지점에서 왔다리 갔다리 하면서 5, 7, 9초에 그 지점에 방문이 가능한거니까요.근데 만약

3지점에 4초에 왔습니다. 동생은 7초에 왔구요.

그러면 불가능합니다. 4, 6, 8... 이렇게만 가능하기 때문이에요. 그렇기 때문에 홀짝을 확인해야 하는 것이고.

지금 K님은 visited 1차원으로 하셨는데 1차원으로 어떻게 이러한 경우의 수를 판단할 수 있나요?

또 질문 있으시면 언제든지 질문 부탁드립니다.

감사합니다.

강사 큰돌 올림.

작성한 질문수