PS/풀이 기록장
-
221027 문제 풀이 기록2022.10.27
-
221026 문제 풀이 기록2022.10.26
-
221025 문제 풀이 기록2022.10.25
-
221024 문제 풀이 기록2022.10.24
-
221022 문제 풀이 기록2022.10.23
-
221021 문제 풀이 기록2022.10.22
-
221014 ~ 221017 문제 풀이 기록2022.10.17
-
221012 문제 풀이 기록2022.10.12
-
221011 문제 풀이 기록2022.10.11
-
221008 문제 풀이 기록2022.10.08
221027 문제 풀이 기록
P3 | 5962 - Generic Cow Protests
풀이 시간: 55분
시도 횟수: 1회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
prefix sum을 만들었을 때, 각 prefix sum 값에 대해 sum[i] <= sum[j]인 모든 i에 대해 DP[j] += DP[i]를 해주자. segtree를 사용하여 이를 최적화할 수 있다.
여담: 원래 f(x, y) = (x부터 y까지 그룹의 합이 0 이상이면 1, 아니면 0) 이라고 할 때 DP[i] = DP[1]*f(2, i) + DP[2]*f(3, i) + ... 방식의 dp를 생각했었는데, 거기서 35분 박고 나서야 다른 방식을 생각하기 시작했다.
자력으로 P3 수준 문제를 풀 수 있게 되었다는 점이 새삼 뿌듯하다. 몇달 전까지만 해도 플레티넘은 쳐다도 못봤었는데...
'PS > 풀이 기록장' 카테고리의 다른 글
| 221029 문제 풀이 기록 (0) | 2022.10.30 |
|---|---|
| 221028 문제 풀이 기록 (0) | 2022.10.28 |
| 221026 문제 풀이 기록 (0) | 2022.10.26 |
| 221025 문제 풀이 기록 (0) | 2022.10.25 |
| 221024 문제 풀이 기록 (0) | 2022.10.24 |
221026 문제 풀이 기록
P3 | 15759 - Talent Show
풀이 시간: 40분
시도 횟수: 1회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
크기가 W 이상인 값들과 미만인 값들의 차이를 토대로, W 이하인 값들에 대한 knapsack DP를 통해 최대값 도출하기.
여담: knapsack을 사용해도 된다는 아이디어를 떠올리기까지 꽤 오랜 시간이 걸렸던 것 같다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221028 문제 풀이 기록 (0) | 2022.10.28 |
|---|---|
| 221027 문제 풀이 기록 (0) | 2022.10.27 |
| 221025 문제 풀이 기록 (0) | 2022.10.25 |
| 221024 문제 풀이 기록 (0) | 2022.10.24 |
| 221022 문제 풀이 기록 (0) | 2022.10.23 |
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 |
221012 문제 풀이 기록
P3 | 6000 - 동전 게임
풀이 시간: 40분 + 30분;;;;
시도 횟수: 분노의 꼬라박기 7회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
dp[i][j] = i번째 턴에 최대 j개까지의 동전을 가져갈 수 있을 때의 최댓값, cnt[i][j] = 그때 가져가는 동전 갯수 를 저장하고 돌리기.
여담: "오늘 좀 잘풀었는데???" 생각하고 첫 제출하니까 MLE떠서 여러번 박았다가 결국 cnt 배열을 short로 선언해서 AC맞았다...
그리고 다른 사람 풀이 보니까 int로 선언해서 31MB 풀이로 풀린게 있던데... :(( 탑다운 DP 못하면 억까 당해야지 뭐...
'PS > 풀이 기록장' 카테고리의 다른 글
| 221021 문제 풀이 기록 (0) | 2022.10.22 |
|---|---|
| 221014 ~ 221017 문제 풀이 기록 (0) | 2022.10.17 |
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
221011 문제 풀이 기록
P4 | 11993 - Circular Barn (Gold)
풀이 시간: 1시간
시도 횟수: 2회
체감 난이도: P4
풀이 쓸 의향: 中
풀이
가장 왼쪽에 근접한 원소를 고르는 것이 최적이다.
여담: 투포인터 구현 실수해서 -1.
다른 사람 코드 보고 알았는데, queue로 하면 훨씬 쉬움... 아니 어떻게 이 생각을 못하지;;;;;;;
'PS > 풀이 기록장' 카테고리의 다른 글
| 221014 ~ 221017 문제 풀이 기록 (0) | 2022.10.17 |
|---|---|
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
| 221008 문제 풀이 기록 (0) | 2022.10.08 |
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
221008 문제 풀이 기록
P4 | 16764 - Cowpatibility
풀이 시간: 1시간
시도 횟수: 4회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
map<vector<int>, int>로 관리하면서 포함/배제의 원리 사용하여 bitmasking 하기
여담: 이런 것도 되는지는 이번에 처음 알았다... 뭐지 이 문제???
'PS > 풀이 기록장' 카테고리의 다른 글
| 221012 문제 풀이 기록 (0) | 2022.10.12 |
|---|---|
| 221011 문제 풀이 기록 (0) | 2022.10.11 |
| 221006 문제 풀이 기록 (0) | 2022.10.06 |
| 221004 문제 풀이 기록 (0) | 2022.10.04 |
| 221003 문제 풀이 기록 (0) | 2022.10.04 |