백준 6198. 옥상 정원 꾸미기

https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

 

- 문제에서 같은 높이의 탑은 옥상을 확인할수 있는지 여부가 안나와 있는데, 질문 게시판에 보면 확인할수 없다고 나와있다.

 

이 문제는 뒤의 빌딩부터 앞으로 탐색해야 하고, 스택에 (빌딩 번호, 높이)를 저장한다. 

i번 탑이 확인할수 있는 옥상의 갯수를 저장하는 mark[] 배열도 만든다.

 

스택의 top의 빌딩의 높이가 탐색중인 빌딩의 높이보다 작으면 계속해서 stack에서 빼주면서 몇개인지 카운팅 해주면 된다.

이때 단순히 스택에서 뺀 갯수가 현재 탐색중인 탑이 확인할수 있는 옥상의 수가 아니라, 스택에서 빼준 탑이 확인할수 있는 옥상의 갯수 즉 mark[] 값도 같이 더해줘야 한다.

왜냐하면 i번탑이 j번 탑보다 높다는 것은 j번 탑은 물론 j번 탑이 확인할수 있는 옥상들도 다 확인할수 있기 때문이다.

 

그리고 답은 long long 형으로 해줘야 한다.

만약 탑의 높이가 1번 탑이 1000000000, 2번 탑이 999999999 ... 80000번째 탑 까지 주어지면 int형을 벗어나는 것을 알 수 있다.