문제 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 브루트포스 알고리즘, 너비 우선 탐색, 조합론, 백트래킹 학생은 전체 25명이다. 여기서 자리를 7개 선택하여 문제의 조건이 맞는지 확인하는 방식으로 답을 구한다. 학생의 수가 많지 않기 때문에 브루트포스로 구현해도 시간 초과는 발생하지 않는다. 자리를 선택하는 방법은 백트래킹을 사용한다. 자리 선택과 해제를 반복하며 자리를 7개 선택했다면 현재 상태가 문제의 조건을 만족하는지 확인한다. 문제의 조건은 다음과 같다. 선택한 자리 모두 상하좌우로 연결되어 ..
문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 수학, 다이나믹 프로그래밍, 조합론 격자상에서 각 칸에 도달할 수 있는 경로의 경우의 수는 다음과 같다. 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 0번 행과 0번 열은 모두 한가지의 방법만 존재한다. (x, y) 칸에 도달할 수 있는 경로의 수는 (x - 1, y) 칸과 (x, y - 1) 칸에 올 수 있는 경우의 수의 합이다. 중간 경로 K를 지나면서 마지막 칸에 도달하는 경우의 수는 (1번 칸에서..
문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 수학, 브루트포스 알고리즘, 조합론, 백트래킹 사전순으로 출력되어야 하므로 미리 입력받은 문자를 정렬시킨 후에 시작한다. 문자열의 길이는 최대 15로 모든 경우의 수를 탐색해도 시간 초과가 발생하지 않는다. 정렬된 문자열의 앞의 문자부터 선택과 선택해제를 반복하며, 선택된 문자열의 길이가 L이라면 정답 조건을 만족하는지 확인한다. 백트래킹으로 문자를 선택한다. void dfs(int index) { // 선택한 문자의 수가 L에 충족한다면 조건에 맞는지 검..
문제 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 조합론, 너비 우선 탐색, 깊이 우선 탐색, 브루트포스 알고리즘 주어진 선거구에서 임의로 몇 개를 선택하여 A구역으로 설정하고, 선택하지 않은 구역은 B구역으로 설정한다. N이 최대 10이므로 모든 경우의 수를 비교해도 시간 초과는 발생하지 않는다. 선거구를 선택할 때는 깊이 우선 탐색의 방식으로 1번 선거구를 선택하고 계산한 다음, 다시 해제하는 방식으로 진행한다. 선택한 선거구가 문제의 조건을 만족하는지 확인해야 한다. 구역은 2개로 나뉘어져야 하므로, 선택한 선거구가 ..
문제 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 수학, 조합론 집합 S에서 숫자 6개를 고르는 경우를 모두 출력하는 문제이다. 조합을 이용하면 간단히 해결할 수 있다. 코드 #include #include #include using namespace std; void Combination(vector arr, vector comb, int r, int index, int depth) { if (r == 0) { sort(comb.begin(), comb.end()); for (int i ..
문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 수학, 다이나믹 프로그래밍, 조합론 다리는 서로 겹쳐질 수 없으므로, 동쪽의 사이트 M개 중에서 N개의 사이트를 선택하는 경우의 수이다. int Combination(int n, int r) { if (n == r || r == 0) { return 1; } else { return Combination(n - 1, r - 1) + Combination(n - 1, r); } } 단순히 위의 함수로만 구하면 시간 초과가 발생한다. 다이나믹 프로그래밍을..
