221025 문제 풀이 기록
P4 | 10019 - Sabotage
풀이 시간: 1시간 고민하다 답지봄
시도 횟수: X
체감 난이도: P2
풀이 쓸 의향: 下
풀이
모든 원소에 대해 x를 빼준 값에서의 최적값을 찾으며 이분탐색 조지기
여담: 또 나만 모르는 웰노운 알고리즘에 교통사고 당한 느낌... 풀이 보고 대체 이런걸 어떻게 생각하지 싶었는데 티어 까고 보니까 P4인거 보고 충격먹었다...
'PS > 풀이 기록장' 카테고리의 다른 글
| 221027 문제 풀이 기록 (0) | 2022.10.27 |
|---|---|
| 221026 문제 풀이 기록 (0) | 2022.10.26 |
| 221024 문제 풀이 기록 (0) | 2022.10.24 |
| 221022 문제 풀이 기록 (0) | 2022.10.23 |
| 221021 문제 풀이 기록 (0) | 2022.10.22 |
221024 문제 풀이 기록
P5 | 1725 - 히스토그램
풀이 시간: 45분
시도 횟수: 10회;
체감 난이도: P5
풀이 쓸 의향: 下
풀이
Monotone Stack으로 stack 관리해주면서 가능한 경우 찾기
여담: 시작점과 끝점인 경우만 세어주고 중간점인 경우를 안 세어놓고 왜 안되는지 오류찾기 하고있었음;; 동일한 문제인 6549번 문제도 겸사겸사 제출함
P3 | 1093 - 스티커 수집
풀이 시간: 1시간 15분
시도 횟수: 10회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
32개의 배열을 16개로 두개씩 나눈 뒤, 2^16가지 각각의 경우에 대해 골랐을 경우의 가격과 가치 값을 저장하자. 왼쪽을 정렬한 뒤 가치는 더 낮은데 가격은 더 높은 경우는 발생하지 않도록 map을 구성한 뒤, 오른쪽 배열에서 이분 탐색을 통해 값 찾아 계산하기
여담: 가지고 있는데 고르지 않았다면 cost를 감소시켜 주는 방식으로 구성했었는데, bit연산을 돌리면서 모든 bit를 순회한 것이 아니라 while (bit>0) 으로 순회하여 가지고 있으나 고르지 않은 경우 몇 가지를 빼놓고 계산하고 있었음.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221026 문제 풀이 기록 (0) | 2022.10.26 |
|---|---|
| 221025 문제 풀이 기록 (0) | 2022.10.25 |
| 221022 문제 풀이 기록 (0) | 2022.10.23 |
| 221021 문제 풀이 기록 (0) | 2022.10.22 |
| 221014 ~ 221017 문제 풀이 기록 (0) | 2022.10.17 |
221022 문제 풀이 기록
P2 | 11982 - Angry Cows (Gold)
풀이 시간: 38분
시도 횟수: 1회
체감 난이도: P2
풀이 쓸 의향: 下
풀이
이분 탐색에 이분 탐색을 싸서 드셔 보세요~ 폭발 범위 R을 이분 탐색으로 구한 뒤, 중간 지점에서 폭발시킨 뒤 좌/우 끝까지 갔는지 여부를 체크하며 둘 다 갔다면 true, 둘 다 못갔으면 false, 둘 중 하나만 갔으면 해당 방향으로 mid를 옮기는 이분 탐색으로 탐색하자.
여담: 오히려 아는게 없어서 자신 있게 달려들 수 있었던 것 같다. 플레 2 문제를 40분 안에 푸는 날이 올 줄이야...!
'PS > 풀이 기록장' 카테고리의 다른 글
| 221025 문제 풀이 기록 (0) | 2022.10.25 |
|---|---|
| 221024 문제 풀이 기록 (0) | 2022.10.24 |
| 221021 문제 풀이 기록 (0) | 2022.10.22 |
| 221014 ~ 221017 문제 풀이 기록 (0) | 2022.10.17 |
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
221021 문제 풀이 기록
P5 | 16440 - 제이크와 케이크
풀이 시간: 15분?
시도 횟수: 1회
체감 난이도: G3(신뢰의 도약), P5(증명까지 포함)
풀이 쓸 의향: 下
풀이
개수가 반반으로 잘리는 연속된 구간이 반드시 하나 있음. 그게 맨 끝이나 처음이면 1개만 잘라도 되는거고, 아니면 두개 잘라야됨.
여담: 전형적인 신뢰의 도약 문제. 솔직히 아이디어는 P5가 아니지만 엄밀히 증명하면서 가면 P5는 그래도 되기는 할듯?
P3 | 15457 - A Pie for a Pie
풀이 시간: 1시간 36분
시도 횟수: 4회
체감 난이도: P2
풀이 쓸 의향: 下
풀이
그래프로 치환한 다음에, map lower_bound 등 다양한 자료구조를 활용하여 BFS 돌리기
여담: 솔직히 BFS라는건 10분만에 깨달았지만 구현하는데 너무 애를 먹어버렸다...
'PS > 풀이 기록장' 카테고리의 다른 글
| 221024 문제 풀이 기록 (0) | 2022.10.24 |
|---|---|
| 221022 문제 풀이 기록 (0) | 2022.10.23 |
| 221014 ~ 221017 문제 풀이 기록 (0) | 2022.10.17 |
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
221014 ~ 221017 문제 풀이 기록
P4 | 15750 - Teleportation
풀이 시간: X
시도 횟수: 7회
체감 난이도: X
풀이 쓸 의향: 下
풀이
좌표의 기울기를 고려하여 스위핑
여담: 스위핑 문제는 익숙치 않아서 좀 많이 헤메다가 답지를 봐버린 문제... 기본 아이디어는 비슷했는데 기울기를 생각을 못했다.
P3 | 5879 - Balanced Cow Subset
풀이 시간: 기억안남
시도 횟수: 5회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
왼쪽 절반 / 오른쪽 절반을 미리 계산해두고, 그 두개를 기반으로 계산하기
여담: 중간에서 만나기 테크닉은 아예 처음이라 얘도 답지를 보고 힌트를 얻었다... 2회 연속 답지보고 문제푸니까 좀 슬프긴 하지만 이렇게라도 배워야 실력이 늘지 뭐... :(
P2 | 9867 - Optimal Milking
풀이 시간: 40분
시도 횟수: 1회
체감 난이도: P2
풀이 쓸 의향: 中
풀이
{왼쪽 / 오른쪽 다고름, 왼쪽만 고름, 오른쪽만 고름, 둘다 안고름} 의 경우의 수에 대해 세그먼트 트리로 관리하며 분할 정복하기
여담: 아니 어떻게 이 문제를 이렇게 풀 수 있다고 생각하지?????????? 솔직히 태그 보고 풀었는데 태그 안봤으면 영원히 못풀었을 것 같은 문제. 대회장에서 이걸 어떻게 생각하지 싶지만... 이런 짓도 가능하다 정도를 생각해 둬야겠다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221022 문제 풀이 기록 (0) | 2022.10.23 |
|---|---|
| 221021 문제 풀이 기록 (0) | 2022.10.22 |
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
| 221008 문제 풀이 기록 (0) | 2022.10.08 |