반응형
Notice
Recent Posts
Recent Comments
Link
안 쓰던 블로그
백준 17408 6549 본문
반응형
17408 수열과 쿼리24
최대값의 위치를 구하는 문제
각 구간의 최대값을 저장한 세그먼트 트리를 만들어서 쿼리를 처리해 주기만 하면 된다
업데이트나 트리 값을 바꿀 때 그냥 리턴하지 않고 임시로 값을 저장해 두고
앞쪽 쿼리, 뒷쪽 쿼리 값을 비교해서 최대값을 갱신하는 식으로 구현했다
근데.. 아래 코드에서
5
5 4 3 9 5
1
2 3 5
하면 14가 나와야 하는데 왜 12가 나오는지 알 수가 없다ㅜ
2 4 5 하면 14가 나오는 거 보면 3-9-5부분이 갱신이 안 된 듯한데 아무리 코드를 봐도 왜 저기만 업데이트가 안 되는지 모르겠다.. 너무 안 풀려서 일단 코드 올리고 패스
6549 히스토그램에서 가장 큰 직사각형
아까 문제가 최대값을 구하는 거라면 이 문제는 최소값을 구하는 문제였다
구하고자 하는 구간에서 만들 수 있는 가장 큰 직사각형의 높이는 바로 높이가 가장 작은 막대가 된다
그러므로 아까와 반대로 최소값을 저장하는 세그먼트 트리를 만들고 해당 높이를 가지고 직사각형 넓이를 출력하면 되었다
반응형
'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
백준 14916 거스름돈을 푸는 다양한 방법 (2) | 2020.09.25 |
---|---|
백준 15721 번데기 (0) | 2020.09.24 |
백준 1699 제곱수의 합 (1) | 2020.06.10 |
솔프드 플레찍기 3일차-17362, 10757, 11943, 5676 etc. (0) | 2020.05.23 |
백준 7578 공장 (0) | 2020.05.22 |
Comments