백준 (225) 썸네일형 리스트형 백준 1413 - 박스 안의 열쇠 www.acmicpc.net/problem/1413 문제의 상황을 상상해보자. 박스에 열쇠를 넣다 보면 열쇠로 다른 박스를 여는 상황이 마치 방향 그래프를 구성하는 것처럼 보임을 알 수 있다. 5번 박스에 5번 열쇠가 있다면 이는 루프를 가진 그래프가 되는 것이다. 박스와 열쇠의 관계는 여러개의 사이클 그래프가(루프 포함) 나오는 것으로 생각할 수 있고, 이는 제1종 스털링 수로 환원된다. 제1종 스털링 수는 말 그대로 n개의 노드에서 m개의 사이클이 형성되는 경우를 나타내는 수열이다. 제1종 스털링 수의 점화식은 다음과 같다. $s(n, k) = (n - 1)s(n - 1, k) + s(n - 1, k - 1) \; (s(0, 0) = 1)$ 한 사이클을 순회하기 위해선 한 개의 폭탄이 필요함을 알 수.. [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] :=.. [ICPC] 백준 2135 - 문자열 압축하기 www.acmicpc.net/problem/2135 다음 dp테이블을 정의한다. dp[i][j] := i번째부터 j번째까지 부분 문자열을 압축한 길이 문자열을 얼마나 압축이 가능한지 파악하기 위해 문자열을 압축할 구간의 길이에 대해 반복문을 돌린다. 문자열을 압축할 수 있는 모든 경우를 탐색하기 위해 해당 길이의 진약수를 모두 구하여 저장한다. 이 진약수들에 대해 반복문을 돌려 구간 내 문자열들이 진약수를 길이로 가지는 부분 문자열들로 압축이 가능한지 확인한다. 예를 들어 길이가 8인 "gogogogo"를 압축한다고 하고 8의 진약수 중 2에 대해 계산하면 "gogogogo"에서 길이 2의 부분 문자열은 "go"가 되므로 부분 문자열로 압축할 수 있음을 확인할 수 있다. 만약 압축이 가능하면 부분 문자열.. [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.. 백준 1754 - 진영 순열 icpc.me/1754 A[0]이 입력으로 주어진 이유 $A[0] \geq 0$ 인 순열들에 대해 진영 순열로 변환하면 다음과 같은 모양새를 띠게 된다. 0 _ _ _ ... / _ 0 _ _ ... / _ _ 0 _ ... / _ _ _ 0 ... 그러면 a + b = c라고 할 때 c-진영 순열이 되는 경우의 수는 0 왼쪽에 있는 순열이 a - 1 진영 순열인 경우 * 0 오른쪽에 있는 순열이 b-진영 순열인 경우 여기서 0 왼쪽에 있는 순열은 0때문에 기존 진영 순열에서 1 더해지므로 a - 1 진영 순열이어야 한다. A[0]인 경우도 따로 처리해야 한다. 이럴 때는 길이 n의 수열이 c-진영 순열인 경우를 구하면 된다. 진영 순열 구하기 기존에 순열에서 확장하는 것을 생각해보자. 다음 대소 관계를.. 이전 1 ··· 28 29 30 31 32 33 34 ··· 45 다음
