본문 바로가기

백준

 (223)
[KOI] 백준 2494 - 숫자 맞추기 www.acmicpc.net/problem/2494 동적계획법을 통해 현재 자물쇠의 상태를 저장하여 푸는 문제이다. 나사가 몇번 회전했는지도 구해야 하므로 dp 테이블 뿐만 아니라 역추적 테이블도 생성해야 한다. 각 테이블의 정의는 다음과 같다. dp 테이블 dp[i][j] := i번째 나사가 현재 상태에서 j번 왼쪽으로 회전한 상태일 때 원하는 숫자로 맞추기 위해 회전한 칸수의 최소 역추적 테이블 backward[i][j] := i번째 나사가 왼쪽으로 j번 회전한 상태일 때 최적해에 도달하기 위해 왼쪽으로 회전한 칸수 바텀 업 dp로 현재 나사에서 원하는 상태를 오른쪽으로 돌려서 맞췄을 때, 왼쪽으로 돌려서 맞췄을 때를 계산해준다. 회전 칸수는 모듈러 연산을 이용해 구해준다. 이 과정에서 최적해가 갱신..
백준 1208 - 부분수열의 합 2 www.acmicpc.net/problem/1208 주어진 조건에서 부분수열을 생성하는 경우는 $2^{40}$으로 단순한 완전 탐색으로 풀 수 없다. 주어진 수열을 절반으로 나눈 상황을 가정해보자. 각 부분에서 수열을 생성하는 경우는 완전탐색으로 $2^{20}$이고 두개의 부분을 탐색해야 하므로 $2 \times 2^{20}$가 되어 각 부분의 부분수열을 구한 후 서로 결합하는 방법으로 문제를 해결 할 수 있게 된다. 이처럼 상태 공간을 반으로 나누고 두 상태 공간의 접점을 탐색하는 기법을 meet in the middle이라 부른다. 주어진 수를 서로 다른 배열에 담아 비트마스킹으로 부분수열의 합을 벡터에 저장하고 각 벡터에서 s의 개수 + 각 벡터에 있는 원소를 더했을 때 s가 되는 경우의 수를 구하..
백준 1514 - 자물쇠 www.acmicpc.net/problem/1514 기본 풀이는 dp이면서도 점화식 진행에 탐욕적 방법이 들어가는 어려운 문제이다.다음 상태로의 진행자물쇠의 왼쪽 디스크부터 오른쪽 방향으로 진행해 잠금을 푼다고 해보자. 그렇다면 첫 시작할 때 기준점은 0번 디스크이고 기준점에서 2번 디스크까지 고려를 해야 한다. 다음 기준점인 1번 디스크로 가기 위해선 0번 디스크가 무조건 알맞은 숫자에 맞춰져 있어야 하고 이는 탐욕적 속성을 만족해야 함을 알 수 있다. 그렇다면 다음 상태는 우선 기준 디스크가 맞춰진 상태에서 오른쪽으로 인접한 두 개의 디스크를 어떻게 회전시킬 것이냐에 따라 갈리게 된다. 기준 디스크를 x, 첫번째 인접 디스크를 y, 두번째 인접 디스크를 z라고 하고 설명하겠다. 1. x와 y, z를 ..
백준 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] :=..

티스토리툴바