[Python] 백준 20928 걷는 건 귀찮아

문제 링크 : https://www.acmicpc.net/problem/20928

20928번: 걷는 건 귀찮아

 

1. 접근 방법

DP나 큐를 활용한 탐색을 고민했는데, 계속해서 시간 초과되었다.

최대 1,000,000까지 탐색을 해야 돼서 N 또는 2N정도로 해결하는 방법을 찾아야 했다

 

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/20000/20928.py

GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다.

📕코드 해설

각 위치별로 최대로 갈 수 있는 위치까지 모두 이동하는 과정을 반복한다.

처음에는 queue를 사용하는 방식도 생각했지만, 가장 오른쪽 위치를 저장하고, 각 위치는 for문을 돌면서 확인했다.

각 위치부터 갈 수 있는 최대 위치까지 저장하며, 2N으로 해결했다.

M위치에 도착하면, 무조건 최소 환승이므로 for문을 종료하고, 또한 각 위치를 한 번도 방문하지 않았는 경우도 종료한다. (더 이상 뒤의 위치로 진행하지 못함)

 

3. 생각 정리

처음부터 시간적인 부분을 고려했다면, 조금 더 빠르게 해결했을 수도 있을 것 같다.

문제를 푸는데 더 집중하다 보니, 오히려 시간과 같은 부분은 별로 신경 쓰지 않고 더 쉬운 방법으로만 풀려고 했던 것 같다. 문제를 어떻게 풀어갈지는 문제의 형식, 입출력도 있지만, 문제의 입력 값의 범위도 크게 영향을 줄 수 있으므로, 조금 더 상세하게 살펴봐야 한다.