순열2 BOJ 15686 치킨 배달 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.. 2020. 12. 25. 순열과 조합 여러 문제들을 풀면서 경우의 수를 따질 때 모든 경우의 수를 따지기 좋은 것이 바로 순열과 조합인 걸 느끼고 정리를 해보려 한다. 중복을 포함하지 않는 순열 중복을 포함한 순열 중복을 포함하지 않는 조합 중복을 포함한 조합 이렇게 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.. 2020. 10. 2. 이전 1 다음