본문 바로가기

누적 합

 (9)
[C++] 2143번 두 배열의 합 https://www.acmicpc.net/problem/2143 25/01/11  이전에 북마크에 넣어두었다가 해결했던 문제다. 두 가지 해결 방법으로 해결할 수 있는데, 일단 나는 첫번째 해결 방법으로만 해결했고, 나머지 하나는 아이디어만 생각해두어서 적어보려고 한다. 문제 접근 방식:  부 배열의 합은 그냥 연속된 구간 합이다. 당연히 나이브하게 하면 시간초과가 날게 뻔하므로, 각각의 누적 합 배열을 $AA, BB$라고 하자. 이제 문제는 $T$가 주어질 때 $AA[i] - AA[j] + BB[p] - BB[q] = T$를 만족시키는 $i, j, p, q$를 구하는 경우의 수 문제로 바뀌게 되었다. 인덱스를 총 $4$개 뽑아야 되는데, 당연히 나이브하게 이걸 $4$개 뽑아서 조건을 만족시키는 것을 ..
[C++] 28774번 Шестизначные документы https://www.acmicpc.net/problem/28774 25/01/02  백준 땅따먹기에서 나온 문제 중 하나인데, 내가 풀었을 당시에는 골드 4였으나 골드 4치고는 굉장히 어렵다고 느꼈던 문제였다. 이러한 아이디어를 복습해보고자 글을 적어본다. 문제 접근 방식:  일단 문제가 러시아어로 적혀있기 때문에 번역을 하면 다음과 같다. 회계사 발레리(Valeiry)는 회계 보고서에서 불일치를 해결하고 있습니다.그는 총 $n$개의 문서를 확인해야 하며, $i$번째 문서는 여섯 자리 정수 식별자 $a_i$를 통해 회사 네트워크에서 접근할 수 있습니다.역전(inversion)이란, 두 번호 $i$와 $j$($i 배열 ${a_i}$의 복잡성(complexity)은 여섯 자리 각각에서 발생하는 모든 역전의..
[Python] 9027번 Stadium https://www.acmicpc.net/problem/9027 24/07/22  지난 주 주간 연습 문제 중 하나로 뽑았던 문제인데, 개인적으로 누적 합 알고리즘을 적용하기에 좋은 문제인 것 같아서 쉽지만 해설을 작성해보고자 한다. 문제 접근 방식:  먼저 문제에서 요구하는 바를 보자. $N$개의 마을 중 한 곳을 선택하여 돔 구장을 짓고자 하고, 각 마을마다 팬이 몇 명 살고있는지, 각 마을의 위치가 어떠한지 또한 주어진다. 각 마을의 위치는 오름차순으로 주어진다.이때 문제에서 요구하는 것은 모든 팬들이 돔 구장으로 모일 때의 이동 거리의 합이 최소가 되도록 돔 구장을 지을 때, 돔 구장의 위치를 출력하는 것이다. 문제 설명의 편의 상 $i$번째 마을의 위치를 $v_i$, 돔 구장의 위치를 $d$,..
[Python] 3673번 나눌 수 있는 부분 수열 https://www.acmicpc.net/problem/3673 24/07/01  간단한 조합론 + 누적 합 문제이다. 업다운 랜디를 하며 풀었다. 문제 풀이 방식 자체는 간단하지만 이를 떠올리는 과정이 좋은 것 같아서 적어보고자 한다. 문제 접근 방식:  요구 사항은 연속하는 부분 수열의 합이 $d$로 나누어 떨어지는 것의 개수를 구하는 것이다.(물론 원래 수열 $A$도 주어지고, $d$값도 주어진다.) 나의 의식의 흐름은 다음과 같았다. 수열의 크기가 테스트 케이스 하나당 최대 5만 정도임. $\rightarrow$ 테스트 케이스 수는 최대 $200$임. $\rightarrow$ 둘을 곱하면 1000만정도 되므로, 하나의 테스트 케이스 당 $\mathcal{O}(N)$의 시간 복잡도로 문제를 해결해..
[Python] 2118번 두 개의 탑 https://www.acmicpc.net/problem/2118 24/05/14  간단한 누적 합 + 두 포인터 연습문제이다. 문제 접근 방식:  두 지점을 $i$와 $j$라고 하고, 편의 상 $i \leq j$라고 가정하자. 원의 둘레를 $T$라고 한다면, 두 지점 사이의 거리는 다음과 같이 정의된다. $$\text{min}(D[j]-D[i] , T-D[j] + D[i])$$ 여기서 $D$는 두 지점의 위치를 나타낸다. 예제 입력을 통해 왜 투 포인터를 써야하는지에 대한 이야기를 해보자.예제 입력에 대한 그림을 그리면 다음과 같다.빨간 지점에서 시작하여 빨간 지점과 가장 멀리 떨어져 있는 곳을 반시계 방향 순으로 찾아보자.그림을 보면 확인할 수 있듯이, 빨간 지점과 가장 멀리 떨어진 지점을 찾을 때까..
[Python] 28303번 자석 https://www.acmicpc.net/problem/28303 28303번: 자석 예제 1의 경우 N극이 3번 칸에 놓이고 S극이 5번 칸에 놓이도록 자석을 설치할 때 1번 현상으로 $a_3=22$의 에너지가 충전되며, 2번 현상으로 $a_5=4$의 에너지가 소모되고, 3번 현상으로 $(5-3)\times 2=4$ www.acmicpc.net 24/02/24 누적 합 응용으로, 아이디어를 떠올리니 쉽게 해결할 수 있었던 문제였다. 문제 접근 방식: 문제를 잘 읽고 분석을 해보았다. 배열을 $A$라고 하고, 배열의 $i$번째 원소를 $a_i$라고 한다면, 문제에서 요구하는 것은 $a_i - a_j - |i-j|K$의 값을 최대화시키는 것이다. $N$의 최댓값이 $500,000$이기 때문에, $\mat..
[Python] 24838번 배열 구간합 놀이 https://www.acmicpc.net/problem/24838 24838번: 배열 구간합 놀이 각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 $10^9+7$로 www.acmicpc.net 23/08/04 내가 있는 스터디 그룹에서 이번 주 주간 문제로 다룬 문제 중 하나로, 구간 합을 적절히 이용한 재미있는 문제이다. 단점이라고 하면, 지문이 너무 길다는 것... 이 글에서는 지문을 전부 이해하고 있다는 가정 하에서 글을 쓸 것이다. 문제 접근 방식: 문제에서 주어진 예제를 잘 이해해 보자. 예제에서는 결론적으로, $1000$을 $2$번 더하고, ..
[Python] 4913번 페르마의 크리스마스 정리 https://www.acmicpc.net/problem/4913 4913번: 페르마의 크리스마스 정리 각 테스트 케이스에 대해서, 한 줄에 L U x y를 출력한다. 여기서 L과 U는 입력으로 주어진 값이고, x는 구간 [L,U]에 포함된 소수의 개수, y는 [L,U]에 포함된 소수중 제곱수의 합으로 나타낼 수 있는 www.acmicpc.net 22/11/13 분명 태그 하나(에라토스테네스의 체)가 보이는 문제여서 접근을 했건만, 2번의 시간초과와 여러 번의 의문의 틀렸습니다를 받고 당황했던 문제이다. 요구하는 선행지식은 누적 합의 개념과 에라토스테네스의 체이다. 문제 접근 방식: 먼저, 구간 내의 소수를 판정해야되고, $L$과 $U$의 범위가 최대 $1,000,000$까지 이므로, 에라토스테네스의 체..

티스토리툴바