220824 문제 풀이 기록

P4 | 1280 - 나무 심기

걸린 시간: 약 40분 (부정확)

체감 난이도: P5 상위권

시도 횟수: 3회

풀이 쓸 의향: 下

풀이

세그트리에 값 하나가 아니라 두개를 넣거나 두개의 세그트리를 따로 만들어서 값을 구하면 되는 문제.

여담: 

나머지 연산 실수때문에 한 번, 값 범위가 0부터 시작인거 못봐서 한 번 틀렸다.

 

 

P5 | 14572 - 스터디 그룹

걸린 시간: 약 30분

체감 난이도: P5 하위권

시도 횟수: 1회

풀이 쓸 의향: 下

풀이

실력 차이가 D 이하인 가장 큰 구간을 투 포인터로 구하고 나서 그 안에 사람들 죄다 돌려보며 구하기

여담: vector<pair<int, vector<int>>>라는 괴상한 자료구조를 만들어서 풀었다.

실력 차이가 D 이하인 모든 구간에서 최대한 많은 사람을 넣도록 투포인터로 풀린다는 아이디어가 쉬운 사람한테는 너무 쉽고, 어려운 사람한테는 너무 어렵게 보일만 한듯.

 

 

P3 | 10542 - 마피아 게임

걸린 시간: 1시간 10분

체감 난이도: P3

시도 횟수: 8회

풀이 쓸 의향: 上

풀이

문제 상황을 그래프로 추상화한 뒤에 관찰을 통해 terminal node를 고르는 것이 최적이라고 증명한 뒤 나머지 남은 cycle은 dfs 돌리면서 size/2만큼씩 더해준다.

여담: 정말 재밌게 푼 문제.

중간에 많이 해메서 좀 코드가 많이 더럽다. 남은 cycle 처리를 이상하게 해서 자꾸 틀리다 결국 발견해서 풀었다.

 

(풀이 메모)

서로 지목하지 않은 사람의 최대 수
그래프로 생각하면

어떤 그룹이 있을 때, 해당 그룹끼리는 서로 화살표가 연결되어있지 않은 최대 크기의 그룹?

1->3
2->3
3->4
4->5
5->6
6->4
7->4

?
노드 N개, 간선 N개인 그래프
사실 유향 그래프일 필요가 없는게 연결되어 있으면 절대 서로가 마피아가 아님.
홀짝놀이

노드 N개, 간선 N개인 무향 그래프에서 서로 이웃하지 않은 노드들의 최대 갯수

간선 N개인게 많이 중요할까
읆...

dfs dp로 되나

cycle 하나 떼면 트리인데...

dp[x][0] : x번 노드가 마피아가 아닐 때, dp[x][1] : x번 노드가 마피아일때 
쩝,,


연결된 개수가 작은걸 제일 먼저 고르는게 무조건 낫나?
그니까 어떤 노드를 고르면 연결된 다른 노드를 절대 고를 수 없는데, 어떤 노드를 고르지 않으면 다른 노드를 고를 수 있는 가능성이 생긴다
가령 1-3 끊으면 1, 3 disable, 2:0, 4:3
2


간선 N개니까 시간 안에 됨
제일 작은거부터 고르되, 제일 작은게 누구인지 계속 봐줘야됨



이거 뭔가 증명이 안되는데...
!
terminal을 고르는 것이 무조건 best이다
그럼 계속 terminal을 찾아서 제거하자