'폴짝폴짝' 태그의 글 목록

📍 문제 탐색하기개구리가 일렬로 놓인 징검다리 사이를 배수 단위로 점프하면서 시작 지점 a에서 목표 지점 b까지 도달하는 최소 점프 횟수를 구하는 문제다.특정 징검다리에 쓰인 숫자를 k라고 하면, k는 그 위치에서 점프할 수 있는 단위를 의미하며, 배수(±k,2k,3k,...)의 형태로만 이동이 가능하다.입력 범위:징검다리 개수 N: 최대 10,000각 징검다리에 쓰인 숫자 k: 최대 10,000a,b: 시작점과 도착점으로 1 ≤ a,b ≤ N가능한 시간복잡도문제를 해결하기 위해 a에서 b까지 탐색해야 한다. O(N): N=10,000: 즉 최대 10,000번의 방문과 연산이 일어난다. 따라서 1억 연산 이하로 충분히 제한 시간 안에 처리가 가능하다.BFS를 이용하여 배수 형태로 이동 가능한 경로만을 ..

알고리즘 2025. 1. 6. 23:50

이전 1 다음