시험공부하기 시러서 쓰는 중
3월 31일에 문제추천 한번 하고
19일간 풀었던 골플 문제 괜찮은걸 한번 써보겠다.
cf) ★는 추천도 기준입니다!
일반적으로 여기 올린건 다 재밌었던 문제들입니다 :)
suapc모의고사 문제
스위핑 + 유니온 파인드
멋진 문제다. 스위핑에 익숙하다면 체감 난이도는 골2~골1정도라고 생각한다.
넘무 넘무 좋은 문제
위상정렬 idea + cycle에서의 따로 판정에 대해 곰곰이 생각해보면 풀린다.
진짜 갓 문제다.
처음에 scc인가? 하고 틀리고
위상정렬 + pq에서 맞왜틀하다가 풀이를 아예 바꿔서 맞았다.
constructive 연습
난이도는 constructive에 익숙하다면, 역시 체감상 좀 낮다.
gcd(n,n+1)=1이라는 idea가 떠올리기 어렵지 않다. (특히 예제에서 대놓고 보여준다)
(꼭 풀어봐요!)
난 이런 문제를 사랑한다. 진짜 내 스타일의 문제다. 언젠가 이런 게임이론 문제를 내야지
잘 생각을 해보자
어떤 게임의 상태에서, 그 상태에 처음 고르는 사람이 이길지 질지는 이미 정해져 있다.
만약 더 큰수가 작은 수의 두배이상이라면 첫번째 사람이 반드시 이긴다.
왜? 원래 더 큰 수가 작은수보다 큰 상태를 A,대소관계가 뒤바낀 상태를 B상태라고 하면, 만약 원래 더 큰수가 작은 수의 두배이상이라면, A->B로 넘어갈때 내가 고를지 상대가 고를지를 선택할 수 있다.
그럼 A->B로 넘어갈때 고른사람이 이기든 지든, 먼저 하는 사람이 이긴다.
두배이상이거나 같은게 아니면 dfs타고 가면 된다!
직관적으로 답을 도출하는 생각 자체는 쉽다고 생각한다.
단지 증명에서는 약간의 조합론과, 수학적 귀납법이 쓰인다.
이 문제 어렵다.
constructive 가 왜 어려운지 여실히 보여준다.
솔직히 풀이 보면 할만해 보이는데 진짜 어렵다.
뭔가 나중에 쓰일수도?
★★★★ Maximum Subarrays (Platinum5)
근래에 봤던 문제중에 젤 멋지다...
진짜 진짜 진짜 갓 문제라고 생각이 든다.
www.acmicpc.net/problem/16494
이 문제도 꽁으로 먹을 수 있다.
한번쯤 누구나 생각해봤을 법한 문제 자체가 Maximum Subarrays이다. dp로 꼭 풀어보자.
전형적이지 않은 dp다. 아이디어가 너무 사랑스럽다
대충 삼각형 그려보면 각 층마다 현재 최댓값, 그리고 총 합이걸 저장해서, 증가수열로 먹어야 함을 알 수 있다.
설명이 이상하긴 한데...어쨌든 dp 다.
또 나왔다! dp!
이건 다시 한번 풀어볼 가치가 있는거 같다.
visited와 queue를 이용해서 어떻게 잘 굴리는데 못 풀어서 풀이를 봤었다.
greedy. 진짜 idea가 미쳤다... 매칭으로 바꾸고 pq쓰는 아이디어에 너무 감명받았다.
나중에 발전시킨 문제를 만들어봐야지.
그리고 이 문제는 가끔씩 할 거 없을때 머릿속에서 곱씹는다 ㅋㅋ 갓 문제
'알고리즘 공부 > Baekjoon online judge' 카테고리의 다른 글
| #2209 버스터미널 (0) | 2021.06.11 |
|---|---|
| #5484 정원 (0) | 2021.06.08 |
| #14684 줄서기 (0) | 2021.06.04 |
| 백준 문제 추천 골3~플3 정도 (3) | 2021.03.31 |
| #10468 숫자뽑기게임 (0) | 2020.11.20 |