본문 바로가기
반응형

Problem Solving242

백준 11376번 열혈강호 2 - C++(cpp) 풀이 1. 할 수 있는 일의 최대 개수는, 최대 매칭의 수와 같다. 2. 각 직원당 최대 2개의 일을 할 수 있으므로, 이분 매칭을 2번 진행한다. 1. 할 수 있는 일의 최대 개수는, 최대 매칭의 수와 같다. 직원 그룹과 일 그룹 사이의 최대 매칭의 수를 구하는 문제이다. 2. 각 직원당 최대 2개의 일을 할 수 있으므로, 이분 매칭을 2번 진행한다. 각 직원당 최대 2개의 일을 할 수 있으므로, 직원을 기준으로 하는 이분 매칭을 2번 진행하여 이루어진 총 매칭의 수를 구해주면 된다. #include #include #include using namespace std; const int MAX = 1001; int N, M; vector works[MAX]; int owner[MAX]; bool visit[.. 2022. 5. 27.
백준 11375번 열혈강호 - C++(cpp) 풀이 1. 직원과 일 사이의 관계를 이분 그래프로 만든다. 2. 이분 매칭 알고리즘을 사용하여 직원 정점 그룹과 일 정점 그룹 사이의 최대 매칭수를 찾는다. 1. 직원과 일 사이의 관계를 이분 그래프로 만든다. 각 직원과 일을 정점으로 생각하고, 각 직원과 그 직원이 할 수 있는 일들을 간선으로 이어 이분 그래프를 만든다. 2. 이분 매칭 알고리즘을 사용하여 직원 정점 그룹과 일 정점 그룹 사이의 최대 매칭수를 찾는다. 최대로 할 수 있는 일의 개수는, 완성된 이분 그래프에서 직원 그룹과 일 그룹 사이의 최대 매칭의 수와 같다. 따라서 이분 매칭 알고리즘을 사용해 최대 매칭 수를 구해주면 된다. #include #include #include using namespace std; const int MAX = .. 2022. 5. 23.
백준 25197번 합주단 곰곰 - C++(cpp) 풀이 1. 두 곰곰이가 있을 때, 둘이 식사할 확률은 1/K 2. 곰곰이 두 마리를 고르는 경우의 수는 N*(N-1)/2 3. 따라서 식사 횟수의 기댓값은 N*(N-1)/2 * (1/K) 1. 두 곰곰이가 있을 때, 둘이 식사할 확률은 1/K 두 곰곰이가 있을 때, 둘이 식사하려면 같은 음을 골라야 한다. 둘이 같은 음을 고를 확률은 K/K^2 = 1/K이다. 2. 곰곰이 두 마리를 고르는 경우의 수는 N*(N-1)/2 또한 곰곰쌍은 총 N*(N-1)/2개 있다. 3. 따라서 식사 횟수의 기댓값은 N*(N-1)/2 * (1/K) 따라서 식사 횟수의 기댓값은 (곰곰쌍의 개수) * (곰곰쌍이 식사할 확률) = N(N-1)/2 * (1/K)이다. #include #include using namespace std;.. 2022. 5. 19.
백준 25174번 힘겨운 쿠기의 식당 개업기 - C++(cpp) 풀이 1. 좌표압축으로 x, y값 범위를 N이하로 줄인 뒤, 각 좌표에 고양이들의 Z값을 기록한 2차원 배열을 board를 만든다. 2. board의 누적합을 기록한 2차원 배열 psum을 만든다. 3. psum을 활용하여 4분면으로 나누는 모든 경우에 대해 E값을 구한 뒤 최솟값을 찾는다. 1. 좌표압축으로 x, y값 범위를 N이하로 줄인 뒤, 각 좌표에 고양이들의 Z값을 기록한 2차원 배열을 board를 만든다. 좌표평면에서 유의미한 포인트들은 고양이가 위치하는 포인트들이다. 유의미한 두 좌표값 사이의 무의미한 좌표값들은 모두 같은 결과를 만들어낸다. 좌표압축으로 x, y값의 범위를 줄여주자. 2. board의 누적합을 기록한 2차원 배열 psum을 만든다. i 사분면에 있는 Z값 합을 구하기 위해 누적합.. 2022. 5. 17.
백준 1701번 Cubeditor - C++(cpp) 풀이 1. dp(a, b): 가장 길게 일치하는 부분 문자열 S[a...], S[b...]의 길이 2. S[a] == S[b] 인 경우 dp(a, b) = 1 + dp(a+1, b+1) 3. S[a] != S[b]인 경우 dp(a, b) = 0 1. dp(a, b): 가장 길게 일치하는 부분 문자열 S[a...], S[b...]의 길이 2번 이상만 등장하면 되므로, 서로 다른 시작점 2개가 있으면 된다. 따라서 dp(a, b)를 위와 같이 정의하자. 2. S[a] == S[b] 인 경우 dp(a, b) = 1 + dp(a+1, b+1) S[a] == S[b]인 경우, 첫 글자가 일치하므로 1+ dp(a+1, b+1)이 된다. 3. S[a] != S[b]인 경우 dp(a, b) = 0 첫 글자부터 일치하지 않는.. 2022. 5. 12.
반응형

티스토리툴바