[BOJ] 백준 6198 옥상 정원 꾸미기 (JAVA)

스택 + DP 활용!

📑 문제

백준 6198 옥상 정원 꾸미기

---

🌱 아이디어

관리인이 보는 방향은 항상 현재 자리 -> 오른쪽으로 본다. 경험상 이러한 구조는 스택으로 구현가능하다.

 

이 문제는 N ≤ 80000 이므로 O(N^2)이 소요되는 알고리즘으로는 풀 수 없다. 즉 이미 계산된 값을 이용해서 다음값을 구하는 

방식으로 중복계산을 줄여 시간을 단축해야 한다.

 

스택과 다이나믹 프로그래밍을 사용해서 풀어보자!

 

예제 1번을 통해 논리의 흐름을 그려 보았다 말로 하는 것보다 효과적일 것이라 생각한다.

너무 길어서 읽기 힘들겠지만 천천히 보다 보면 흐름이 보일 것이다

 

1. dp 배열 = 각 위치에서 볼 수 있는 옥상 수

2. stack1, stack2 = 빌딩 번호

3. arr1 배열 = 빌딩 높이 

 

1. 초기 상태

 

5번 빌딩과 6번 빌딩의 높이를 비교합니다

1 ) 5번 빌딩이 더 클 경우 = dp[5] += dp[6] + 1 & stack2의 6번 빌딩 제거 후 5번 빌딩 저장

2 ) 5번 빌딩이 더 작을 경우 = stack1의 5번 빌딩제거 후 stack2에 5번 빌딩 저장.

 

1번 연산을 실행합니다.

 

 

2. dp[5]번 업데이트 결과

4번 빌딩과 5번 빌딩의 높이를 비교합니다

1 ) 4번 빌딩이 더 클 경우 = dp[4] += dp[5] + 1 & stack2의 5번 빌딩 제거 후 4번 빌딩 저장

2 ) 4번 빌딩이 더 작을 경우 = stack1의 4번 빌딩제거 후 stack2에 4번 빌딩 저장.

 

2번 연산을 실행합니다.

3. dp[4]번 업데이트 결과

 

3번 빌딩과 4번 빌딩의 높이를 비교합니다

1 ) 3번 빌딩이 더 클 경우 = dp[3] += dp[4] + 1 & stack2의 4번 빌딩 제거 후 3번 빌딩 저장

2 ) 3번 빌딩이 더 작을 경우 = stack1의 3번 빌딩제거 후 stack2에 3번 빌딩 저장.

 

1번 연산을 실행합니다.

 

4. dp[3]번 업데이트 결과

 

2번 빌딩과 3번 빌딩의 높이를 비교합니다

1 ) 2번 빌딩이 더 클 경우 = dp[2] += dp[3] + 1 & stack2의 3번 빌딩 제거 후 2번 빌딩 저장

2 ) 2번 빌딩이 더 작을 경우 = stack1의 2번 빌딩제거 후 stack2에 2번 빌딩 저장.

 

2번 연산을 실행합니다.

 

5. dp[2]번 업데이트 결과

 

1번 빌딩과 2번 빌딩의 높이를 비교합니다

1) 1번 빌딩이 더 클 경우 = dp[1] += dp[2] + 1

1 - 1) 1번 빌딩과 3번 빌딩의 높이를 비교합니다

1 - 2) dp[1] += dp[3] + 1

 

2) 2번 빌딩이 더 작을 경우 = stack1의 2번 빌딩제거 후 stack2에 2번 빌딩 저장.

 

1, 1 - 1, 1 - 2번 연산을 함께 실행합니다.

 

답을 찾았다 !

위 흐름을 반복하면 O(N+N) 정도의 시간복잡도를 가지며 답을 구할 수 있다.

설명이 길었다 이제 구현만 하면 된다!

 

---

 

🌱 코드 및 풀이

 

위 그림과 함께 사용된 자료구조 및 배열을 매칭해서 본다면 이해하는 것은 어려울 게 없다.

20번째 줄 while문은 위 그림의 5번째 그림 조건 1, 1-1, 1-2와 같은 조건을 만족시키기 위해 반복적으로 처리한다

 

한 가지 더 주의해야 할 점은

 

N = 80000 이면서,  모든 건물이 "8000, 7999,7998... 1"  즉 높이가 내림차순으로 나열되어 있다면

이는 등차수열의 합 과 같은 효과(?)를 본다

( 첫 번째 건물은 자신을 제외한 나머지 건물 옥상을 다 볼 수 있고 2번, 3번 건물도 자신 보다

아래의 수많은 건물 옥상을 볼 수 있기 때문이다.)

 

N = 80000일 때 등차수열의 합은 = 80000/2(1+80000) =  40000(80001) =  32,000,040,000

N^31 int 형 범위를 훨씬 넘어버린다.

즉 건물옥상의 합을 담는 변수는 long 형으로 선언해 주자!

필자는 4%에서 바로 틀렸다

---

🌱 느낀 점

자료구조 섹터에 중점을 두고 연습 중이라 그런지 스택을 두 개 사용해서 풀려고 노력했다

사실 굳이 스택이 2개까지는 필요 없을 것 같다 ㅎㅎ 

 

내 풀이로도 스택 1개로도 풀 수 있는데 포스팅을 하다 보니 코드의 허점이 보인다 ㅎㅎ

포스팅을 하면서 스스로 코드리뷰와 생각의 흐름을 적다 보니

복습하는 좋은 습관이 생긴 것 같다 끝!