www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 추가 주어진다면 오름차순 정렬을 해주고 현재까지의 누적합 + 1 이 현재의 추보다 더 크다면 그 누적합 + 1 이 구할 수 없는 최솟값이 된다. 그 이하의 수들은 현재까지의 추들로 모두 조합할 수 있다. #include #include using namespace std; int ar[1001]; int main() { int n; cin >> n; for (int i = 0; i > ar[i..

여러 문제들을 풀면서 경우의 수를 따질 때 모든 경우의 수를 따지기 좋은 것이 바로 순열과 조합인 걸 느끼고 정리를 해보려 한다. 중복을 포함하지 않는 순열 중복을 포함한 순열 중복을 포함하지 않는 조합 중복을 포함한 조합 이렇게 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++) ..

간단한 BFS 문제였다. 근데 문제에서 주의해야 할 점이 있다. 전역 변수로 선언할 경우 반드시 solution 내에서 초기화를 시켜줘야 한다. 이것만 주의한다면 나머진 쉽게 풀리는 문제다. #include #include #include using namespace std; vector solution(int m, int n, vector picture) { int number_of_area = 0; int max_size_of_one_area = 0; vector vis(101, vector(101, false)); queue Q; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; int tmp = 0; for (int i = 0; i < m; i++) { ..

문자 배열이 주어지면 각 자릿수로 만들 수 있는 모든 경우의 수를 따져서 소수가 되는 수가 몇 개인지 따져보는 문제다. 소수는 에라토스테네스의 체로 쉽게 구할 수 있지만 문제는 '어떻게 모든 경우의 수를 따지는가'이다. 우리는 두 가지 경우로 풀 수 있다. dfs로 풀던가 next_permutation으로 풀던가 둘 중 하나로 풀면 된다. 나는 next_permutation으로 풀었다. #include #include #include #include using namespace std; vector sieve; void era(int n) { sieve.resize(n + 1, true); sieve[0] = sieve[1] = false; for (int i = 2; i * i

참여자와 완주자 배열이 주어지면 완주하지 못한 선수의 이름을 리턴하면 되는 쉬운 문제다. 난 map을 이용해서 해결했는데 다른 사람의 풀이를 보니 두 배열을 정렬하고 이름이 같지 않다면 그 이름을 리턴해주는 식으로 풀었다. #include #include #include using namespace std; string solution(vector participant, vector completion) { string answer = ""; map m; for (auto i : participant) { m[i]++; } for (auto i : completion) { m[i]--; } for (auto i : participant) { if (m[i] == 1) answer = i; } return..