[BOJ] 백준 6198 옥상 정원 꾸미기 (JAVA)
Algorithm/- Baekjoon2024. 3. 5. 11:00[BOJ] 백준 6198 옥상 정원 꾸미기 (JAVA)

📑 문제🌱 아이디어관리인이 보는 방향은 항상 현재 자리 -> 오른쪽으로 본다. 경험상 이러한 구조는 스택으로 구현가능하다. 이 문제는 N ≤ 80000 이므로 O(N^2)이 소요되는 알고리즘으로는 풀 수 없다. 즉 이미 계산된 값을 이용해서 다음값을 구하는 방식으로 중복계산을 줄여 시간을 단축해야 한다. 스택과 다이나믹 프로그래밍을 사용해서 풀어보자! 예제 1번을 통해 논리의 흐름을 그려 보았다 말로 하는 것보다 효과적일 것이라 생각한다.너무 길어서 읽기 힘들겠지만 천천히 보다 보면 흐름이 보일 것이다 1. dp 배열 = 각 위치에서 볼 수 있는 옥상 수2. stack1, stack2 = 빌딩 번호3. arr1 배열 = 빌딩 높이   5번 빌딩과 6번 빌딩의 높이를 비교합니다1 ) 5번 빌딩이 더 클..

image