본문 바로가기
반응형

Problem Solving/BOJ228

백준 5676번 음주 코딩 - C++(cpp) 풀이 1. 구간 내 음수의 개수를 저장하는 세그먼트 트리와 0의 개수를 저장하는 세그먼트 트리를 둔다. 2. 주어진 쿼리의 구간에 0이 하나도 없는 경우, 음수의 개수가 홀수개이면 결과값도 음수, 짝수개이면 양수이다. 3. 주어진 쿼리의 구간에 0이 한 개 이상 있는 경우, 결과값은 0이다. 1. 구간 내 음수의 개수를 저장하는 세그먼트 트리와 0의 개수를 저장하는 세그먼트 트리를 둔다. 값의 변경이 계속 이루어지는 상황에서 구간에 대한 쿼리를 수행해야 하므로 세그먼트 트리를 이용하여 해결할 수 있다. 구간곱이 양수인지, 음수인지, 0인지만 알면 되기 때문에 음수의 개수, 0의 개수를 기록하는 두 개의 세그먼트 트리를 만들어준다. 2. 주어진 쿼리의 구간에 0이 하나도 없는 경우, 음수의 개수가 홀수개이면 결.. 2022. 5. 31.
백준 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.
반응형

티스토리툴바