반응형 알고리즘207 백준 2632번 피자판매 - C++ 풀이 1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다. 2. A피자에서 연속된 조각을 선택하는 모든 경우에 대해 목표합을 만들기 위한 경우의 수를 더한다. 1. B피자에서 연속된 조각을 선택하는 모든 경우를 구해 각 연속합을 만들 수 있는 경우의 수를 구해둔다. 두 피자에서 연속된 조각을 선택하는 모든 경우를 고려하면 O(N^4)의 시간 복잡도가 소요된다. 따라서 두 피자를 각각 탐색한 뒤, A피자를 기준으로 대응하는 B 피자의 경우의 수를 구하는 방법을 사용하여 O(N^2)에 해결할 것이다. mp[i] = (B 피자에서 연속합이 i가 되도록 조각을 고르는 경우의 수)라고 하자. B 피자에서 연속된 조각을 선택하는 모든 경우에 대해 그 합을 구해 mp .. 2022. 9. 2. 백준 14867번 물통 - C++ 풀이 1. 항상 두 물통 중 한 물통은 꽉 차있거나 비어있다. 2. BFS를 사용해서 {0, 0}에서 {C, D}로 가는 최단 거리를 구한다. 1. 항상 두 물통 중 한 물통은 꽉 차있거나 비어있다. 주어진 연산을 사용하면 항상 두 물통 중 한 물통은 꽉 차있거나 비어있어야 한다. 따라서 상태를 나타낼 때, 아래와 같은 3가지 정보만 있으면 된다. 한 물통에 들어있는 양 x 그 물통이 A물통인지 B물통인지 여부 반대 물통이 비어있는지 꽉 차있는지 여부 두 물병에 들어있는 물의 양 정보 대신 위의 정보를 사용하여 상태를 나타내면 상태 개수를 N^2개에서 4N개로 줄일 수 있다. 2. BFS를 사용해서 {0, 0}에서 {C, D}로 가는 최단 거리를 구한다. 위의 사실을 이용해서 상태 노드를 나타내고 BFS를 사.. 2022. 9. 1. 백준 16134번 조합 - C++ 풀이 1. nCr = n! / (n-r)!r! 의 정의대로 계산한다. 2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다. 1. nCr = n! / (n-r)!r! 의 정의대로 계산한다. 조합 nCr의 정의대로 반복문을 통해 계산할 것이다. 2. 나눗셈은 모듈러 곱셈 역원을 이용하여 계산한다. (A*B) mod C = (A mod C) * (B mod C) mod C 임을 이용하여 곱셈을 계산하고, 나눗셈의 경우 1,000,000,007이 소수이므로 모듈러 곱셈 역원을 이용하여 계산한다. 모듈러 곱셈 역원은 분할정복을 이용한 거듭제곱을 사용해서 구하면 된다. #include using namespace std; typedef long long ll; const ll MOD = 1000000007; ll pow.. 2022. 8. 30. 백준 3020번 개똥벌레 - C++ 풀이 1. 종유석과 석순을 따로 저장한다. 2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다. 3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다. 1. 종유석과 석순을 따로 저장한다. 두 장애물의 방향이 다르므로 종유석과 석순을 따로 저장한다. 2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다. 종유석은 끝부분이 h 미만인 것들을 파괴해야 하고, 석순은 끝부분이 h 초과인 것들을 파괴해야 한다. 따라서 종유석과 석순을 각각 정렬한 뒤, 이분 탐색을 이용하여 파괴해야 하는 개수를 각각 구해주면 된다. 3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다. 총 H개의 구간에 대해 파.. 2022. 8. 27. 백준 1744번 수 묶기 - C++ 풀이 1. 양수는 양수끼리 묶고, 음수는 음수끼리 묶는다. 2. 1번 과정을 수행할 때는 수들을 정렬한 뒤, 절댓값이 큰 수부터 차례로 두 개씩 묶는 것이 최선이다. 3. n+1 > n*1이므로 1은 항상 묶지 않고, 0은 음수랑만 묶는다. 1. 양수는 양수끼리 묶고, 음수는 음수끼리 묶는다. 양수와 음수를 묶으면 음수가 되어 묶지 않고 그냥 더하는 것보다 합이 더 작아진다. 따라서 양수는 양수끼리, 음수는 음수끼리만 묶도록 한다. 2. 1번 과정을 수행할 때는 수들을 정렬한 뒤, 절댓값이 큰 수부터 차례로 두 개씩 묶는 것이 최선이다. 이때 합이 최대가 되려면 절댓값이 큰 수부터 차례로 묶어야 한다. 만약 숫자가 홀수개라 마지막 수가 남는다면 그냥 더해준다. 3. n+1 > n*1이므로 1은 항상 묶지 않고.. 2022. 8. 26. 이전 1 2 3 4 5 6 7 ··· 42 다음 반응형
