02.01 ~ 02.07 PS

며칠 또 게으르게 풀은 것 같다..

근데 슬슬 P3 Queue에서 어려운/생소한 문제들만 남아가지고 더딘 것 같기도 하다.

 

• [P4] 국회(http:boj.kr/1226) : 새벽에 잠결에 PC방에서 켜고 찬우형 성준이형이랑 같이 잡았다. 의석 수 기준인데 그냥 정당 수 기준으로 봤나 그래서 왜 그리디가 아니냐라고 헛소리하다가 정신 차리고 냅색으로 풀어서 맞혔다. 추천!
• [P3] 수열의 개수 NKD(http:boj.kr/1336) : 디미고 정올반에서 20분 안에 풀어보라고 시켰다고 하길래 20분 걸고 시도했다. 20분 줬다길래 그냥 세그 DP인줄 알고 슥슥 했는데 문제를 잘못 읽었다. 다시 읽고 오래 걸려서 풀었다. 약간 코포틱한 DP인데 푸는 맛이 있었다. 추천!
• [P5] Arithmetic Progressions(http:boj.kr/16740) : 백준에 있는 타일 밟기, 등차수열이랑 같은 문제이다. 2022년 3월 PS일지에 나름 구체적으로 풀이를 정리해뒀다. 버추얼 도는데 읽고 코딩하고 맞히기까지 다 합해서 거의 6~7분 안에 한 것 같다.
• [P5] Emergency Evacuation(http:boj.kr/16741) : $S$ 시간 내에 모든 승객은 복도와 연결되어 있다. 첫 $S$ 시간은 näive하게 시뮬레이션 한다. 그리고 나면 복도와 연결된 상태에서 각 복도의 위치마다 트래픽을 기록한 수열 같은걸 만들 수 있는데, 이 상태에서 값을 잘 변화시켜서 풀 수 있다. 내가 좀 이상하게 푼 것 같더라. 정해는 뭔가 독특한 발상으로 별 구현 없이 되는 듯 하다.
• [P3] 랜덤 걷기(http:boj.kr/3946) : 제한이 약간 이상해서 $O(n^3)$ DP가 가능하다. 하지만 이건 P5따리 재미없는 버전이라고 생각. $O(n^2)$으로 푸는 풀이가 말이 안 된다. 추천!