coci (5) 썸네일형 리스트형 백준 12116 - Uzastopni https://www.acmicpc.net/problem/12116 힌트더보기$a$부터 연속된 $k$개의 정수의 합을 구하려면 다음과 같은 식으로 풀 수 있다. $a \times k + \frac{k \times (k - 1)}{2}$ 그 합이 $N$이 되려면 $N = a \times k + \frac {k \times (k - 1)}{2}$ 를 만족해야 함을 알 수 있다.풀이힌트에서 언급한 식 $N = a \times k + \frac{k \times (k - 1)}{2}$ 를 만족하는 $a$를 구해보도록 하자. 식을 정리하면 $2N = k(2a + k - 1) \rightarrow 2a = \frac{2N}{k} - k + 1$가 되므로 적절한 범위의 $k$에 대해 $2a$가 짝수인 경우를 모두 찾아.. [COCI] 백준 3055 - 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제를 잘 이해해야 한다. 이동과 범람이 동시에 일어난다고 되어있다. 주어진 조건대로 이동을 잘 시뮬레이션하기 위해서는 이동을 먼저 한 다음 범람을 일으켜야 한다. 이 순서로 BFS를 진행해서 이동한 위치에 범람이 될 예정인지 아닌지는 신경쓰지 않고 큐에 넣는다. 그다음 범람을 수행한다. 그렇게 이동이 1회 끝난 뒤 다음 큐에서 꺼낼 때 범람된 상태면 해당 노드를 탈락시키고 다음 노드를 꺼내서 확인하면 된다... [COCI] 백준 2836 - 수상 택시 https://www.acmicpc.net/problem/2836 관찰 사람을 어떻게 태우던지 목적지에 도착해야 되므로 최소 M만큼의 거리를 이동한다. 어차피 배도 M으로 향해야 하므로 M방향으로 가는 사람들은 무시하고 역방향으로 가는 사람만 고려하면 된다. 역방향으로 가는 사람들은 어떻게 되는걸까? 한번 지나간 곳을 또 지나가는 것은 최적해에 도달할 수 없음을 떠올릴 수 있고 그러면 사람이 오르내리는 사건이 발생하는 최대 구간을 만드는 것을 생각할 수 있다. 최적해에 관한 예시로 5와 7 지점에서 역방향으로 가려는 손님이 있는데 5를 태운 다음 7을 태우지 않고 뒤로 돌아간다면 7을 태우기 위해 다시 그만큼 거리를 이동해야 하므로 최적해가 아님을 알 수 있다. 따라서 스위핑을 통해 역방향 노선을 적절히.. [COCI] 백준 10740 - ACM www.acmicpc.net/problem/10740 문제 소개 Zagreb 대학교에 속한 스테판, 이반, 구스타프가 모로코에서 열리는 ICPC WF를 참석한다. 그들의 전략 가이드 고란은 필승전략을 가져왔는데 그 전략은 다음과 같다. 대회 극초반에 각 멤버가 n문제의 난이도를 분석한다. (1부터 5까지 있으며 5가 제일 어렵다.) 그리고 각 팀원이 풀 문제를 연속적으로 분배한다. (1 2 3 4 5 번이 있으면 1 2 / 3 / 4 5 처럼 분배할 수 있다.) 어떤 사람이라도 문제를 풀지 않는 경우는 없어야 한다. 이렇게 문제를 분배할 때 각 팀원이 담당한 문제의 분석 난이도 합이 최소가 되는 분배 방법을 찾아야 한다. 풀이 - 탑 다운 dp 다음 이차원 dp 테이블을 생각해보자. dp[i][j] :=.. [COCI] 백준 3020 - 개똥벌레 icpc.me/3020 종유석과 석순을 살펴보면 어떤 식으로 나열되어 있든 부숴야 될 갯수에는 변함이 없다는 것이다. 그 즉슨 종유석과 석순을 정렬하고 이진 탐색을 통해 어떤 높이에서 몇개 부숴야 하는지 확인하면 빠르게 풀 수 있음을 알 수 있다. 1부터 h까지 반복문을 돌려 해당 높이에서 최소한으로 부술 수 있는지, 최소한으로 부술 수 있는 경우가 몇개인지 확인하면 AC를 받을 수 있다. 시간복잡도 $O(HlogN)$ 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include using namespace std; int n, h; int br.. 이전 1 다음
