220922 문제 풀이 기록

P3 | 1395 - 스위치

풀이 시간: X

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

레이지 세그 연습 문제

여담: USACO 랜덤 돌렸더니 나왔길래 레이지 세그 연습하는셈 치고 풀었음. 근데 생각보다 구현에 애를 먹어서 다른 코드들 참고하며 풀었음... 사실상 내가 푼 게 아닌 느낌이긴 하지만 레이지 세그 연습용으로는 괜찮았다.

 

 

 

P4 | 15587 - Cow at Large (Gold)

풀이 시간: 30분

시도 횟수: 2회

체감 난이도: P4

풀이 쓸 의향: 中

풀이

BFS와 DFS를 잘 쓰까서, DFS로는 리프 노드에서 다른 모든 노드로 가는 최소 거리를, BFS로는 시작 위치에서 다른 모든 노드로 가는 최소 거리를 구한 뒤에 노드 개수 세주기

여담: 풀이를 생각하기엔 까다롭지는 않았으나, 구현을 어떤 방식으로 해야 할 지 고민을 하게 만든 문제. 풀이 과정도 재밌고 구현도 재밌었다.

 

 

 

P2 | 12008 - 262144

풀이 시간: 50분

시도 횟수: 2회

체감 난이도: P2

풀이 쓸 의향: 上

풀이

연속한 동일한 수의 그룹이 짝수개라면 그냥 그리디하게 합쳐주면 되고, 홀수개라면 배열을 두개로 쪼개서 왼쪽 / 오른쪽 나눠서 계속 계산해주기.

여담: 풀이를 생각하고, 해당 풀이의 정당성을 증명하고, 해당 풀이의 시간/공간 복잡도가 시간/메모리 제한 안에 부합하는지 확인하고, 적절하게 구현하기까지 과정이 즐거웠다. 특히 문제도 짧고 간결해 이해하기도 쉬웠다.

근데 태그가 내 생각과는 다르게 박혀 있길래 다른 사람들의 풀이도 봤는데, 관찰까지는 다들 비슷했으나 나는 단순 구현으로, 다른 사람들은 여러 테크닉을 응용한 dp정도로 푼 모양이다. 그 풀이들도 다들 훌륭한 것 같다.

 

 

 

P5 | 1572 - 중앙값

풀이 시간: 15분

시도 횟수: 1회

체감 난이도: P5

풀이 쓸 의향: 下

풀이

사탕상자 문제처럼 sum seg에 이분탐색 구현하기

여담: 자기 전 마지막 한 문제 풀고 가려고 랜덤 돌렸는데 나왔다... 그냥 연습삼아 슥 풀고 감.