2017. 7. 25. 16:39ㆍ알고리즘 문풀/BOJ 연습
*이 문제 set은 백준 온라인 저지에서 랜덤을 돌려서 푼 문제들입니다. 풀이를 좀 포멀하게 적고 싶어서 쉬운 문제라도 모두 풀이를 상세하게 기록할 예정이니, 그게 마음에 들지 않으신 갓갓분들은 살포시 뒤로가기를 눌러 주세요.
1. 수열 축소
문제 : http://icpc.me/2237
풀이 :
얘는 고1때 정올을 딱 시작할 때쯤 풀지 못하고 넘겨버린 문제. 사실 CON이란 연산이 전혀 대단하지 않다는 것만 알면 된다.
CON연산을 수행한 결과는 수열의 인접한 원소 사이에 + 또는 -의 부호를 적절히 삽입하여 계산한 식이다. (단, 앞에는 반드시 -가 붙는다) 그래서 dp table을 잡고,
까지 적절히 계산한 값이 가 되게 하는 의 부호로 생각하면 시간 안에 dp table을 채울 수 있고, 답이 에서 역추적을 하면서 각 수열에 붙어야 하는 부호를 알아낸다.
인 경우, 왼쪽에 있는 가장 가까운 값이 -인 인덱스 에 대해 를 호출하면 된다.
인 경우는 언젠가 을 호출하면 된다.
+인 경우부터 오른쪽에서 왼쪽으로 쫙 훑고, -의 개수만큼 1을 출력해주면 답이 된다.
Time Complexity :
2. NMK
문제 : http://icpc.me/1201
풀이 :
쉽게 보고 풀다가 MWT 여러 번 낸 문제. 그리디에 왜 이렇게 약한지 모르겠다...
일단 그런 수열이 존재하지 않을 조건을 명확히 하는 게 중요하다.
(1) 인 경우, 와 의 교집합에 최소 2개의 원소가 존재하게 되는데, 이를 라고 하면 수열 에는 겹치는 원소가 없으므로
인 동시에 여야 하므로 모순.
(2) 인 경우,
Erdos-Szekeres theorem ( https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem )에 의해 M+1 이상의 길이를 갖는 LIS, 또는 K+1이상의 길이를 갖는 LDS가 존재하게 된다.
두 조건을 모두 만족할 경우 쉽게 수열을 construct할 수 있다.
로 잡으면 된다. 아마도?
Time Complexity :
'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글
7/30 ~ 7/31 연습 (0) | 2017.08.01 |
---|---|
7/29 연습 (0) | 2017.07.30 |
7/27~7/28 연습 (0) | 2017.07.29 |
7/26 연습 (0) | 2017.07.27 |
7/25 연습 (0) | 2017.07.26 |