[백준 - 21279] 광부 호석
문제:https://www.acmicpc.net/problem/21279
처음에 잘못된 가정을 하고 풀었다.
끝지점을 한 광물에 찍어놓고 그 사이의 광물만 세면서 답을 구하려 했다.
이를 구현하기 위해 y좌표를 기준으로 저장하며, value와 count의 값을 가지는 세그먼트 트리를 만들고, x좌표가 작은 순서대로 방문하여 사이의 광물을 세서 풀었다.
이렇게 하고보니 예제1부터 답이 안나오더라.
캐는 범위의 끝지점이 꼭 광물이 있는곳이 아닐 수도 있다. 예제 1이 그렇다.
그래서 급하게 이분탐색을 추가하여 현재 보는 광물의 y좌표와 10만 사이에서 count가 초과하지 않으면서 가장 value가 높은 곳을 찾았다(by 세그트리).
그랬더니 13/16 만큼 맞았다. (채점 너무 친절한거 아닙니까?!)
또 생각해보니 다음과 같은 반례가 있었다.
화살표 친 놈을 볼 때, 같은 x 좌표이면서 그 위에 있는 광물은 추가를 안한 상태이다.
이 때 y좌표 끝까지 이분탐색을 해버리면 엄연히 존재하는 광물을 무시하게 된다.
그래서 이분탐색에서 right 를 다음과 같이 설정했다.
다음 점의 x좌표가 같을 경우 [다음 점의 y좌표-1] else 10만
화살표 친 점이 확인 못한 영역은 그 다음 점에서 탐색 할 것이다.
당연하지만 이게 정해는 아니다.
정해는 우선순위큐를 사용하여 x좌표가 낮은 순대로 탐색하고,
광물이 초과할 경우 y좌표가 큰놈부터 빼주는데 코드가 엄청 간결하더라.
내 코드의 시간복잡도는 O(Nlog^2N) 이다.
[백준 - 2672] 여러 직사각형의 전체 면적 구하기
문제: https://www.acmicpc.net/problem/2672
스위핑을 생각 못해서 정직한 풀이를 생각하다보니 남들보다 좀 귀찮게 풀었다.
사각형을 입력 받을 때 마다, 기존에 존재 했던 사각형들과 매칭하면서 최대 4개로 분리시켰다.
그리고 이번에 입력받은 사격형은 그대로 집어넣어 겹치는 부분이 없게 만들었다.
검은색이 기존에 있던 사각형이고, 빨간색이 이번에 받은 사각형이라면 다음과 같이 검은 사각형을 분리해저장한다.
모두 입력받고나서 존재하는 모든 사각형의 넓이를 합하면 된다.
출력조건이 까다로워서 좀 많이 틀렸다...
소수점 한자리까지 밖에 안주어지는데 그냥 10 곱해서 int로 바꾸고 풀었어야 했는데
괜히 double로 했다가 고생했다.
[백준 - 7981] 장비를 정지합니다
문제: https://www.acmicpc.net/problem/7981
1번 장비의 약한충격과 강한충격의 비용중 어느게 싸게 먹히는지 알아내야 한다.
결과적으로 약한 충격에 연결된 장비들을 dfs를 하면서 사이클이 형성 되는 지점은 무조건 강한 충격, 아니면 계속 따라 가서 비용을 비교했다.
여기에 메모이제이션을 더해 동적계획법으로 풀었다.
특이한 점은 visited는 별 의미가 없고 finished만 고려해서 사이클을 찾을 수 있다. 한번 방문 했던 점이라 하더라도, finished가 되었다면 다시 방문하지 않은 것 처럼 탐색하면 되기 때문이다.
