www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 생각보다 쉽게 풀었다. 치킨집이 총 13개까지 주어지는 조건을 봤고, 치킨집과 집을 매칭 시키는 것이 combination을 떠올리게 한다. 따라서 그래프 탐색이 아니라 조합, 경우의 수로 접근해봤다. 일단 보자마자 집을 원소로 가지는 a벡터, 치킨집을 원소로 가지는 b벡터를 인자로 받아 각 원소를 \(O(N^2)\)으로 순회하며 가장 작은 치킨 거리를 찾아 리턴해주는 함수를 만들었다. 1..

www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net DP를 연습하던 중에 재미있는 풀이로 풀 수 있어서 가져와 봤다. k가 존재하면 (0, 0)에서 k가 존재하는 인덱스 (i, j)까지 의 길 찾기 경우의 수 \(nCk\)로 구하고 그 k에서 (n - 1, m - 1)까지의 경우의수를 또 구하면 된다. 나이브하게 풀면 오버플로가 나고 dp테이블에 조합을 저장해 두고 풀어야 한다. 1 2 3 4 5 6 7 8 9 10 11 1..

여러 문제들을 풀면서 경우의 수를 따질 때 모든 경우의 수를 따지기 좋은 것이 바로 순열과 조합인 걸 느끼고 정리를 해보려 한다. 중복을 포함하지 않는 순열 중복을 포함한 순열 중복을 포함하지 않는 조합 중복을 포함한 조합 이렇게 4가지로 나눌 수 있을 것 같다. 각각의 방법에 대해서 DFS와 c++의 algorithm 헤더 파일의 next_permutation을 사용해서 만들 수 있다. 모든 순열과 조합에 대해서 n개 중에서 m개를 뽑는 경우의 수를 보자. 중복을 포함하지 않는 순열(DFS) #include using namespace std; int ar[10], n, m; bool vis[10]; void DFS(int cnt) { if (cnt == m) { for (int i = 0; i < m..

www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 49가지 수 중에서 6개를 뽑아 출력하는 문제다. 백트래킹을 이용한 조합 문제였다. n과 m을 푼 게 도움이 됐다. #include #include #include using namespace std; void dfs(int cnt, int idx, vector& ar, vector& tmp, vector vis) { if (cnt == 6) { for (int i = 0; i < cnt; i++) ..