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 공부를 시작해보려고 한다.