[백준] 2493 탑 (C++)

bfs를 통해 백준 문제를 풀어보자

[백준] 2493 탑

문제

조건

1. N개의 탑이 왼쪽에서 오른쪽으로 일렬로 배치되며, 각 탑은 왼쪽으로 레이저를 발사한다.
2. 레이저 신호는 자신보다 먼저 있는(왼쪽에 있는) 더 높은 탑에서 수신되며, 가장 가까운 탑만 신호를 받는다.
3. 각 탑이 보낸 레이저 신호를 어떤 탑이 수신하는지 출력해야 한다.

풀이 방식

이 문제의 조건은 간단하지만 풀이 방식에서 시간초과를 생각해서 풀이 하는 것이 주요했다. N의 최대가 500,000이기에 만약 \(O(N^2)\)의 복잡도로 풀이하게 되면 시간초과가 난다는 점을 생각해보면 일반적으로 생각하는 타워를 순차적으로 돌아가면서 찾는 방식이 아닌 다른 방식을 생각해야 했다.

그중에서 자료구조 stack을 활용해서 이전 타워중에 현재 타워보다 작은 타워를 지워버리게 되면 입력 받음과 동시에 이전의 타워들중에서 현재 타워의 신호를 수신할 타워의 index를 찾아낼 수 있는 방식으로 풀이했다.

자세한 코드는 아래를 확인…

답안

참고자료

백준 탑 풀러가기