6198 옥상 정원 꾸미기 / c++ / Gold5 / 31분
문제 및 코드
풀이 과정
동적 프로그래밍
- N개의 건물의 높이 배열이 주어진다. 각 건물에서 오른쪽으로 볼수 있는 옥상의 개수의 총합을 출력하는 문제. (단, 자기자신보다 크거나 같은 높이의 건물 이후의 건물은 볼 수 없다.)
- 원래 문제 알고리즘은 스택이었다. 그런데 나는 동적 프로그래밍으로 풀었다.
- 건물 높이 배열을 역방향으로 순회한다.
- 자기 자신보다 크거나 같은 건물의 위치를 BlockPos로 명명
- 현재 i번째 건물일 때, BlockPos의 초기값은 i + 1로 설정
- 만약 BlockPos 가 N보다 작고, Heights[i] > HeightsBlockPos, BlockPos = DP[BlockPos]로 설정, 이를 whlie문으로 반복
- 즉, BlockPos로 설정된 건물보다 내가 크다면, 그 BlockPos의 BlockPos(적어도 BlockPos보다 큰 건물)를 다시 탐색하는 것이다.
- 그렇게 결정된 최종 BlockPos 를 DP[i]에 저장 (이 때, 만약 제일 오른쪽 건물이거나, 나보다 높은 건물이 없다면 DP[i]는 N이 된다.)
- 그 후 Answer 에 BlockPos - i - 1 값을 더해준다. (i번째 기준 바로 옆 건물(i+1)이 나보다 크다면, 결국 볼 수 있는 건물이 없다는 뜻이므로 0이 더해짐)
- 역방향 순회가 끝난 후 Answer를 출력
- 해결
회고
- 이 문제도 예전에 비슷한 문제를 풀어봤기 때문에 어렵지 않게 공식을 도출해낼 수 있었다. 하지만 코딩 과정에서 부등호나 로직 순서를 잠시 헷갈려서 시간을 잡아먹었다.
- 알고리즘 카테고리가 스택으로 되어 있어서, 다른 사람들이 어떻게 푸는지 봤더니 정방향 순회를 하면서 스택에 현재 건물보다 낮은 건물을 다 pop하고, 스택의 크기를 Answer 에 더해주는 식으로 풀었다.
- 이러면 스택에는 현재 건물보다 큰 건물만 남기 때문에, 현재 건물을 볼 수 있는 왼쪽 건물의 수를 더해가면서 푸는 방식이었다.
- 또 하나의 새로운 풀이법을 배울 수 있었다.
