반응형 누적합4 백준 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. 백준 14476번 최대공약수 하나 빼기 - C++ 풀이 1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다. 2. i번째 수를 제외한 나머지 수들의 gcd는 gcd(prefixGCD[i-1], suffixGCD[i+1])이다. 3. 각 수를 제외하는 모든 경우를 탐색하며 최대공약수가 최대가 되는 경우를 찾는다. 1. 누적 gcd인 prefix gcd와 suffix gcd 배열을 구해둔다. 어떤 수를 제외한 나머지 수들의 gcd를 O(1)에 구하기 위해 누적 gcd 배열을 활용할 것이다. A[0]~A[i] 까지의 최대 공약수는 prefixGCD[i], A[i]~A[N-1]까지의 최대공약수는 suffixGCD[i]라고 할 때, prefix GCD 배열과 suffix GCD 배열을 구해준다. 이 과정의 시간 복잡도는 O(N) 2. i번째 .. 2022. 6. 13. 백준 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. 백준 10986번 나머지 합 - C++(cpp) 풀이 1. s부터 e까지의 구간합이 M으로 나누어 떨어지려면, psum[e] % M = psum[s-1] % M이어야 한다. 2. psum[i] % M = psum[j] % M 인 (i, j) 쌍의 개수를 구한다. 3. psum[i] % M 자체가 0인 경우도 추가로 카운트한다. 1. s부터 e까지의 구간합이 M으로 나누어 떨어지려면,psum[e] % M = psum[s-1] % M이어야 한다. i까지의 누적합을 psum[i]라고 하자. s부터 e까지의 구간합은 psum[e] - psum[s-1]이 된다. 이 구간합이 M으로 나누어 떨어지려면, (psum[e] - psum[s-1]) % M = 0이어야하므로, psum[e] % M = psum[s-1] % M이 성립해야 한다. 2. psum[i] % M = p.. 2022. 4. 14. 이전 1 다음 반응형
