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 |