PS/풀이 기록장
-
221209 문제 풀이 기록2022.12.09
-
221208 문제 풀이 기록2022.12.08
-
221206 / 221207 문제 풀이 기록2022.12.07
-
221128 문제 풀이 기록2022.11.28
-
221125 문제 풀이 기록2022.11.25
-
221124 문제 풀이 기록2022.11.24
-
221118 문제 풀이 기록2022.11.18
-
221117 문제 풀이 기록2022.11.17
-
221029 문제 풀이 기록2022.10.30
-
221028 문제 풀이 기록2022.10.28
221209 문제 풀이 기록
P3 | 4243 - 보안 업체
풀이 시간: 30분 + 극한의 뇌절
시도 횟수: 2회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
무조건 왼쪽 혹은 오른쪽 둘 중 하나의 방향을 고르므로, dp[l][r][k] = l부터 r까지 방문했고, k=0이면 l, k=1이면 r에 현재 위치하고 있을 때의 지연 시간 합의 최소 로 저장해두고 dp를 돌리자.
여담: "n은 100... t는 1500000이니까..? nt=15억? 음 최댓값은 INT_MAX로 박아도 되겠군!"..... 풀고 나서 내가 틀렸나 하면서 식을 이리저리 살펴보며 코드 잘못짠거 있나 계속 돌려보고 논리가 틀렸나 하고 이것저것 확인해봤는데... 반례도 이것저것 넣어보면서 손으로 해보면서 뭐가 틀린 부분이 있나 해봤는데..........
P5 | 2150 - Strongly Connected Component
풀이 시간: X
시도 횟수: X
체감 난이도: X
풀이 쓸 의향: X
풀이
SCC 예제 문제
여담: 플3랜디를 몇번 돌려봤는데, 이제 슬슬 새로운 알고리즘들을 배워야 할 시기인것 같아서 SCC / 2-sat / LCA / sparse table / MCMF 공부를 시작해보려고 한다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221208 문제 풀이 기록 (0) | 2022.12.08 |
|---|---|
| 221206 / 221207 문제 풀이 기록 (0) | 2022.12.07 |
| 221128 문제 풀이 기록 (0) | 2022.11.28 |
| 221125 문제 풀이 기록 (0) | 2022.11.25 |
| 221124 문제 풀이 기록 (0) | 2022.11.24 |
221208 문제 풀이 기록
P4 | 5461 - 고용
풀이 시간: 굉장히 오랜 시간
시도 횟수: 굉장히 많은 횟수
체감 난이도: P3
풀이 쓸 의향: 中
풀이
Q 1당 드는 비용을 K라고 하면, 어떤 고용인 조합 X에 대해 K=max(S_i/Q_i) for i <= X가 된다. K를 오름차순으로 정렬하여 순서대로 생각해보면, K * sum(Q) <= w여야 하고, 이때 최적의 방법은 지금까지 나온 Q 중 가장 작은 고용인들만 순서대로 최대한으로 고용하면 된다. K가 커지면 지금 사용한 Q값보다 더 큰 Q를 절대로 더하지 않으므로 (본인 차례 제외), pq를 사용하여 구현할 수 있다.
여담: "만약 고용할 수 있는 노동자의 수가 같다면, 노동자들에게 최소 비용을 지급하는 고용 방안을 원하며"... 이걸 못봐서 다 풀어놓고 대가리박고 있었다.
P3 | 11873 - 최대 직사각형
풀이 시간: 30분 + a (예전에 풀다 때려쳤던 경험 있음)
시도 횟수: 1회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
히스토그램(1725번) N번씩 해주기
여담: 예전에 이 문제 봤을때는 2차원 구간합 구현해놓고 "이걸 어케 풀어;"하면서 던졌었는데, 다시 보니까 바로 "그 문제" 삘이 나서 바로 풀었다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221209 문제 풀이 기록 (0) | 2022.12.09 |
|---|---|
| 221206 / 221207 문제 풀이 기록 (0) | 2022.12.07 |
| 221128 문제 풀이 기록 (0) | 2022.11.28 |
| 221125 문제 풀이 기록 (0) | 2022.11.25 |
| 221124 문제 풀이 기록 (0) | 2022.11.24 |
221206 / 221207 문제 풀이 기록
P3 | 20945 - 의자 게임
풀이 시간: 1시간 + a
시도 횟수: 2회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
문제를 정리하면, 반복되는 수 없이, 최대-최소 차이가 K이하인 최대 크기를 x라 하면, 답은 K-max(x)이다. 반복되는 수 없음은 set을 사용하여 구현하였고, 최대-최소 차이는 segtree와 단조성을 활용한 이분탐색으로 구현하였다.
여담: 처음에 아예 틀리게 생각했었는데, 그 풀이에서 조금씩 뻗어가면서 풀이에 접근해갔다. set 안쓰고 무지성 n^2으로(미쳤었던듯) 제출했다가 TLE 한번 뜨고, 다시 set으로 구현해서 AC.
P3 | 23834 - 커여운 키위
풀이 시간: 45분?
시도 횟수: 2회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
dp[i] = i번째에서 음수로 이동하는 경우의 이동 거리 최댓값 으로 정의하자.
그러면, dp[i] = max(dp[j] + sum[i-1] - sum[j]) - a[i] = max(dp[j] - sum[j]) + sum[i-1] - a[i] for i-m <= j < i 로 정의되고, dp[j] - sum[j]값을 segtree를 활용하여 저장해주면 답은 max(dp[i] + sum[i+m] - sum[i] + b[i], sum[i] - sum[j] + dp[j] for j<i) 이다.
여담: segtree + dp 유형의 문제. 태그를 보니까 덱을 이용한 dp라고도 하던데... 세그트리가 참 만능인듯 싶다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221209 문제 풀이 기록 (0) | 2022.12.09 |
|---|---|
| 221208 문제 풀이 기록 (0) | 2022.12.08 |
| 221128 문제 풀이 기록 (0) | 2022.11.28 |
| 221125 문제 풀이 기록 (0) | 2022.11.25 |
| 221124 문제 풀이 기록 (0) | 2022.11.24 |
221128 문제 풀이 기록
P4 | 2532 - 먹이사슬
풀이 시간: 약 30분
시도 횟수: 4회 + 1회 (992ms로 통과한 뒤에 좌표압축 다시 구현해서 제대로 풀었음)
체감 난이도: P3 하위권
풀이 쓸 의향: 中
풀이
중복값 없앤뒤 시작점은 오름차순, 끝점은 내림차순으로 정렬하면 반드시 앞쪽에 놓여진 동물이 뒷쪽에 놓여진 동물보다 상위에 있게 되므로, 끝점을 원소로 하는 MAX seg를 구현하자.
여담: 시즌 292148호 태그랑 딴판으로 문제풀기 성공! 문제 풀다가 "이거 lis 비슷하게 될것 같은데...?" 싶다가 갑자기 세그트리 풀이로 틀어버렸다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221208 문제 풀이 기록 (0) | 2022.12.08 |
|---|---|
| 221206 / 221207 문제 풀이 기록 (0) | 2022.12.07 |
| 221125 문제 풀이 기록 (0) | 2022.11.25 |
| 221124 문제 풀이 기록 (0) | 2022.11.24 |
| 221118 문제 풀이 기록 (0) | 2022.11.18 |
221125 문제 풀이 기록
P4 | 3043 - 장난감 탱크
풀이 시간: 30~40분
시도 횟수: 3회
체감 난이도: P4 하위권
풀이 쓸 의향: 下
풀이
모든 x값과 y값을 1~N이 하나씩 들어가는 순열으로 만들자. 1부터 N까지 숫자를 올리며 가장 가까운 탱크를 옮기는 것이 움직임의 최소 횟수임은 쉽게 알 수 있다. 이때, 움직이는 과정에서 동일한 칸에 탱크가 겹치지 않도록 L, R, U, D 각각에 대해 L, U는 초기 위치에 대한 오름차순으로, R, D는 초기 위치에 대한 내림차순으로 정렬하여 출력하자.
여담: 동일한 칸에 겹치는 탱크를 고려 안해서 -1, push_back(y)자리에 (x) 집어넣어서 -1... 복붙하다 실수했다..
'PS > 풀이 기록장' 카테고리의 다른 글
| 221206 / 221207 문제 풀이 기록 (0) | 2022.12.07 |
|---|---|
| 221128 문제 풀이 기록 (0) | 2022.11.28 |
| 221124 문제 풀이 기록 (0) | 2022.11.24 |
| 221118 문제 풀이 기록 (0) | 2022.11.18 |
| 221117 문제 풀이 기록 (0) | 2022.11.17 |
221124 문제 풀이 기록
P3 | 1523 - 종점
풀이 시간: 25분
시도 횟수: 1회
체감 난이도: ??
풀이 쓸 의향: 下
풀이
N이 충분히 작으므로, 모든 노드를 비트마스킹으로 종점이 아닌 노드들을 세자.
종점이 아닌 노드들만으로 서로를 연결할 수 있으며, 종점인 노드들은 모두 종점이 아닌 노드와 적어도 하나의 간선으로 연결되어 있으면 연결 그래프이고, 아니라면 연결 그래프가 아니다.
또한, 이미 연결 그래프인 경우에서는 어떻게 하더라도 종점 두 개는 반드시 만들 수 있으므로 정답의 최솟값은 2로 맞춰두면 편하다. (위 알고리즘으로 답이 2 미만으로 나오는건 n=2인 경우밖에 없으므로 별로 의미는 없긴 하다)
여담: 사실 난이도 플레 랜덤으로 슬쩍 가리고 풀었는데... 풀고 나서 이게 이 난이도가 맞나 싶었던 문제. 경험상 이런 생각이 들던 문제들은 보통 다른 사람이 기여했던게 맞았어서 난이도 기여에서는 손 뗐다.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221128 문제 풀이 기록 (0) | 2022.11.28 |
|---|---|
| 221125 문제 풀이 기록 (0) | 2022.11.25 |
| 221118 문제 풀이 기록 (0) | 2022.11.18 |
| 221117 문제 풀이 기록 (0) | 2022.11.17 |
| 221029 문제 풀이 기록 (0) | 2022.10.30 |
221118 문제 풀이 기록
P4 | 1604 - 도망자 원숭이
풀이 시간: 약 1시간
시도 횟수: 2회
체감 난이도: P4
풀이 쓸 의향: 下
풀이
괴롭힘 시간을 오름차순 정렬한 뒤, k번째 이하의 괴롭힘만 받았다고 했을 때의 거리를 나타내어 플로이드-워셜 적용시키기.
여담: 플로이드-워셜 알고리즘이 어떻게 동작하는지 다시 찬찬히 이해해본 다음에야 풀 수 있었던 문제. 훌륭한 문제인듯.
'PS > 풀이 기록장' 카테고리의 다른 글
| 221125 문제 풀이 기록 (0) | 2022.11.25 |
|---|---|
| 221124 문제 풀이 기록 (0) | 2022.11.24 |
| 221117 문제 풀이 기록 (0) | 2022.11.17 |
| 221029 문제 풀이 기록 (0) | 2022.10.30 |
| 221028 문제 풀이 기록 (0) | 2022.10.28 |
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 |