분류 전체보기
-
221117 문제 풀이 기록2022.11.17
-
221029 문제 풀이 기록2022.10.30
-
221028 문제 풀이 기록2022.10.28
-
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
221117 문제 풀이 기록
P5 | 10605 - 드래곤 죽이기
풀이 시간: 25분
시도 횟수: 2회
체감 난이도: P5
풀이 쓸 의향: 下
풀이
바로 초기 위치에서 드래곤을 바로 죽일수 있을만큼의 용사 vs 그냥 max(N_i) 에 대해, 드래곤들을 연결된 도시들 별로 따로따로 pq에 넣고 계산하며 그리디하게 찾기
여담: P4 기여가 박혀있었는데... 물론 분리집합이나 이분탐색 등 여러 풀이들이 아른거려서 그정도 난이도로 보일수 있겠지만 가장 간단한 풀이는 구현도 그렇게 어렵지 않고 해서 P5로 기여했더니 P5+4.9로 내려감.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221124 문제 풀이 기록 (0) | 2022.11.24 |
|---|---|
| 221118 문제 풀이 기록 (0) | 2022.11.18 |
| 221029 문제 풀이 기록 (0) | 2022.10.30 |
| 221028 문제 풀이 기록 (0) | 2022.10.28 |
| 221027 문제 풀이 기록 (0) | 2022.10.27 |
221029 문제 풀이 기록
P3 | 10759 - 팰린드롬 경로 3
풀이 시간: 1시간 10분 + a
시도 횟수: X
체감 난이도: P3
풀이 쓸 의향: 下
풀이
중앙에 있는 부분부터 시작해서, 현명하게 DP값 찾기. 특정 위치 (y, x)까지 도달했을 때의 경로의 갯수를 저장해 주면 됨.
여담: 맞왜틀 후 답지보고 풀었음 : 풀이는 맞았었는데 구현에서 고꾸라져서 틀린 것으로 보임 :(
P3 | 18264 - Moortal Cowmbat
풀이 시간: 42분
시도 횟수: 3회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
일단 플로이드-워셜로 모든 M*M개의 경우에 대해 치환하는 최솟값을 구해두고 나서, DP[i][j] = i번째 index까지를 문자 j로 바꿨을 때의 최솟값 으로 두자. 부분 합을 토대로 [x, y] 구간의 모든 문자열을 j로 바꾸는 비용은 O(1) 안에 구할 수 있다.
dp[i][j] = min(sum[i][j], dp[i-1][j] + sum[i][j] - sum[i-1][j])로 초기화해둔 다음에,
dp[i][j] = min(dp[i][j], dp[i-K][x] + sum[i][j] - sum[i-K][j]) for all 0 < x < M;
으로 두면 O(NM^2)으로 해결 가능.
여담: 문제 제목 보고 혼자 쪼갰음. 어떻게 문제 이름을 저렇게 짓지 ㅋㅋㅋ
처음에 n m 헷갈려서 -1, dp 배열 초기화 제대로 안해줘서 -1;
그보다 요즘 DP 문제들을 엄청 많이 풀고있는 느낌이다. 흠,,
'PS > 풀이 기록장' 카테고리의 다른 글
| 221118 문제 풀이 기록 (0) | 2022.11.18 |
|---|---|
| 221117 문제 풀이 기록 (0) | 2022.11.17 |
| 221028 문제 풀이 기록 (0) | 2022.10.28 |
| 221027 문제 풀이 기록 (0) | 2022.10.27 |
| 221026 문제 풀이 기록 (0) | 2022.10.26 |
221028 문제 풀이 기록
P3 | 5834 - Cow Run
풀이 시간: 42분
시도 횟수: 3회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
dp[l][r][x][y] = dp[왼쪽에 남은 갯수][오른쪽에 남은 갯수][이전에 좌 골랐으면 0, 아니면 1][지금 좌 고르는거면 0, 아니면 1] 로 dp 계산하기 -> dp[l][r][x][y] = abs(현재위치 - 이전 위치) * (l+r) + min(dp[l-1][r][y][0], dp[l-1][r][y][0]) (x==0일때). 무조건 왼쪽에서 제일 가까운 소나 오른쪽에서 가장 가까운 소를 골라야 한다는 사실을 토대로 dp 계산.
여담: dp식 세우면서 pos의 유일성을 해치는 방식으로 짜서 -1, long long 안써서 -1
그보다 원래 DP 엄청 못했는데 이제 조금씩 감을 잡는 느낌... :)
'PS > 풀이 기록장' 카테고리의 다른 글
| 221117 문제 풀이 기록 (0) | 2022.11.17 |
|---|---|
| 221029 문제 풀이 기록 (0) | 2022.10.30 |
| 221027 문제 풀이 기록 (0) | 2022.10.27 |
| 221026 문제 풀이 기록 (0) | 2022.10.26 |
| 221025 문제 풀이 기록 (0) | 2022.10.25 |
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 |