정리
백준 2493번: 탑 본문
백준 2493번: 탑
2493번: 탑
KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
www.acmicpc.net
- 배열과 스택을 사용하여 풀었다.
- height배열에 빌딩의 높이를 저장한다.
- height[i] > height[i-1] 일 경우 (i = N~1), stack에 height[i]와 i를 저장한다.
- height[i] < height[i-1] 일 경우 (i = N~1), height[i]의 레이저는 height[i-1]이 수신하므로 answer[i] = i-1 이다. 또한 stack에 저장된 다른 값들도 height[i-1]에 수신되는지 확인해야 한다. 만약 stack에 저장된 값이 height[i-1]보다 작으면 answer[s.pop().idx] = i-1으로 해주면 된다. stack의 가장 첫 번째 값이 height[i-1] 보다 크다면 그 뒤에 저장된 값들도 모두 height[i-1]보다 크기 때문에 더 이상 확인할 필요가 없다.
- 아래의 코드는 통과는 되지만 상당히 느리다. 더 빠른 방법을 생각해 봐야 할 것 같다.
'Programming > 백준 BOJ' 카테고리의 다른 글
| 백준 1654번: 랜선 자르기 (0) | 2021.01.05 |
|---|---|
| 백준 1789번: 수들의 합 (0) | 2020.12.25 |
| 백준 14488번: 준오는 급식충이야!! (0) | 2020.09.30 |
| 백준 2109번: 순회강연 (0) | 2020.09.30 |
| 백준 1461번: 도서관 (0) | 2020.09.28 |
'Programming/백준 BOJ' Related Articles
more
Comments