문제 링크입니다: https://www.acmicpc.net/problem/8982
8982번: 수족관 1
입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(1 ≤ N ≤ 5,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난다. 즉, 시작 꼭짓점과 마지막 꼭짓점의 가로줄 번호는 항상 0이다. 수족관의 경계를 이루는 변은 꼭짓점 (0, 0)부터 시작하는 데, 수직선분으로 시작하여 수평선분과 수직선분이 번갈아가며 반복되다 수직선분으로 끝난다. 따라서 수직선분이 수평선
www.acmicpc.net
별 다른 알고리즘을 요구하진 않지만 생각을 좀 해봐야하는 문제였습니다.
우선, 전처리가 이 문제의 핵심인 것 같습니다.
시작 좌표와 끝 좌표를 제외하고는 각각이 똑같은 높이이기 때문에 두 개의 좌표를 입력 받고 해당 구간의 깊이를 똑같은 깊이로 초기화하는 것이 핵심이였습니다.
깊이를 전처리한 후에는 각각의 구멍에 대해 빠져나간 물의 깊이를 아래와 같이 처리하면 됩니다.
1. 구멍은 항상 해당 칸의 바닥에 위치하고 있기 때문에 어디 칸에 속하는지만 확인하면 됩니다.
2. 해당 칸을 기준으로 왼쪽과 오른쪽을 탐색하며 빠져나간 물의 깊이를 파악하면 됩니다.
3. 현재 보고 있는 구멍을 기준으로 높이는 더 이상 깊어질 수 없으므로 min, 빠져나간 물의 깊이는 최대 높이에 대해서 봐야하기 때문에 max 처리해줍니다.
마지막으로, (해당 칸의 최대 깊이 - 해당 칸에서 빠져나간 물의 깊이)의 합을 출력해주면 됩니다.
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 17140번 이차원 배열과 연산 (2) | 2019.05.08 |
|---|---|
| 백준 12904번 A와 B (0) | 2019.05.06 |
| 백준 15361번 Izbori (5) | 2019.05.03 |
| 백준 15360번 Rasvjeta (2) | 2019.05.03 |
| 백준 4574번 스도미노쿠 (0) | 2019.05.03 |