220913 문제 풀이 기록

G4 | 1967 - 트리의 지름

풀이 시간: X

시도 횟수: 1회

체감 난이도: G4

풀이 쓸 의향: 下

풀이

1번 노드에서 가장 멀리 있는 x번 노드, x번 노드에서 가장 멀리 있는 y번 노드 두 노드를 이은 거리가 지름임

여담: 바로 아래 적을 문제 풀기 전에 겸사겸사 제출함.

 

 

 

P5 | 13016 - 내 왼손에는 흑염룡이 잠들어 있다

풀이 시간: 약 1시간 + a

시도 횟수: 1회

체감 난이도: P5

풀이 쓸 의향: 下

풀이

트리 지름의 말단 노드 두개 잡고 2N번 순회하면서 최대 길이 찾기

여담: 어제 코포하기 전에 잠깐 보다가 코포시간되서 그냥 코포치러 가느라 못풀었던 문제. 트리의 지름 쓰는 문제인건 알 수 있었는데 아직도 트리의 지름 문제를 안풀었어서 트리의 지름 구하는 법을 모르고 있었다.

 

 

 

G5 | 15681 - 트리와 쿼리

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: G5

풀이 쓸 의향: 下

풀이

그냥 트리 순회하면서 값 저장하기

여담: Tree DP를 거의 안풀었던 것 같아서 잡아봤는데, 이게 DP인가....? 싶었음.

 

 

 

 

P4 | 17082 - 쿼리와 쿼리

풀이 시간: 아이디어 1시간 + 디버깅 2시간

시도 횟수: 무수히 많음

체감 난이도: P4

풀이 쓸 의향: 下

풀이

구간은 그리디하게 정렬한 뒤 앞에서부터 잡으면 되고, 구간 병합한 뒤에 주어지는 쿼리에 따라 값 바꿔끼며 최대값 관리하기. multiset 쓰면 편리함

여담: 오늘 이 문제 때문에 시간 너무 많이 날렸는데... 왜 자꾸 segfault 뜨는지 모르겠어서 무지성 제출 박으니까 갑자기 됐다. 아니 근데 왜 됐지??

참고로 풀이할때 세그트리를 썼었는데, 태그를 보아하니 세그트리는 필요 없었던 모양...

 

 

 

P4 | 10649 - 프리스비

풀이 시간: 약 1시간 + 20분

시도 횟수: 1회

체감 난이도: P4

풀이 쓸 의향: 中

풀이

(키+무게) 내림차순으로 정렬 후, (총 무게) - (키 + 무게) 값으로 정답 구하기. N<=20이므로 비트마스킹으로 모든 집합 순회하면서 브루트 포싱하면 풀림.

여담: 예전에 한번 봤다가 못풀겠어서 버려뒀는데, 마침 랜덤으로 돌렸는데 나오길래 풀어보니까... 20분만에 금방 풀이가 나왔다. 그리디가 참 한번 막히면 너무 막히고, 한번 잘풀리면 너무 잘풀리는 느낌이다.

 

 

 

P5 | 2123 - 인간 탑 쌓기

풀이 시간: 1시간 + X

시도 횟수: 2회 + 1회

체감 난이도: P5

풀이 쓸 의향: 中

풀이

(키+무게) 내림차순으로 정렬 후, (키 + 무게) - (총 무게) 값으로 정답 구하기. 

여담: 프리스비 문제 풀다가, 뭔가 비슷한 문제를 저번에 시도했다가 틀렸던 기억이 나서 찾아보니 있었다. 간단한 처리를 제외하면 거의 동일한 문제지만, 그래도 프리스비 쪽이 더 어렵지 않나 싶다. 그보다 프리스비랑 인간 탑 쌓기 둘 다 예전에 풀다가 던졌던 문젠데, 오늘 하루 종일 백준만 풀어서 머리가 잘돌아가나 싶다.