누적 합

문제 2725번: 보이는 점의 개수 첫째 줄에 테스트 케이스의 개수 C(1

문제 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 풀이 수학, 정수론, 누적 합 문제이다. for (int i = 1; i T; // 먼저 약수들의 합을 구해야 한다. // 약수들의 합을 O(N * log(N))의 시간복잡도로 구한다. for (int i = 1; i

문제 풀이 누적 합 문제이다. 보드가 격자로 칠해져 있기 때문에, 칠해야 하는 칸을 누적 합으로 구해야 한다는 것을 생각하기 힘들었다. 보드판의 첫 칸이 검정색인 보드와, 하얀색인 보드로 나눠서 생각한다. (i, j)칸 까지, 각 보드칸에서 칠해야 하는 칸의 수를 누적 합으로 구해놓는다. i + j 가 짝수라면, 첫 칸의 색과 같은 색상이어야 한다. 홀수라면, 다른 색상이어야 한다. 이런 식으로 (i, j)칸을 탐색하며 누적 합을 구한다. 구한 2차원 누적 합에 K X K칸을 잘라냈을 때의 누적 합의 최솟값을 찾는다. 코드 #include #include #include using namespace std; char board[2001][2001]; int sum_black[2001][2001]; int..

문제 풀이 누적 합 문제이다. https://kantatatam.tistory.com/143 [백준][C++] 30508: 고인물이싫어 문제 풀이 그래프 탐색, 누적합 문제이다. 횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 kantatatam.tistory.com 2차원 배열의 누적 합을 구하는 문제로 위 문제와 풀이가 같다. 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; c..

문제 풀이 다이나믹 프로그래밍, 누적 합 문제이다. 완전 탐색으로 해결하려고 하면 O(N * N)으로 시간 초과이다. 배열을 두 개를 사용하여 문제를 해결해야 한다. 첫 요소가 왼쪽인 배열. 왼쪽이 과반수인 배열. (left) 첫 요소가 오른쪽인 배열. 오른쪽이 과반수인 배열. (right) 전체 배열을 탐색하면서 돌상이 왼쪽인 경우에는, left 배열의 깨달음의 양이 1 증가하면서, right 배열의 깨달음의 양이 1 감소한다. 돌상이 오른쪽인 경우에는, left 배열의 깨달음의 양이 1 감소하면서, right 배열의 깨달음의 양이 1 증가한다. 현재 배열의 깨달음의 양이 0미만이라면 해당 배열을 버린다. 현재 배열 2개의 깨달음의 양의 최대값이 답이다. 코드 #include #include using..

문제 풀이 누적 합 문제이다. https://kantatatam.tistory.com/143 [백준][C++] 30508: 고인물이싫어 문제 풀이 그래프 탐색, 누적합 문제이다. 횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 kantatatam.tistory.com 2차원 배열에서의 누적 합을 구하는 문제로 위의 30508번 문제와 거의 동일하다. 코드 #include using namespace std; int nums[1001][1001]; int sum[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.t..

문제 풀이 그리디, 누적 합, 많은 조건 분기 문제이다. N의 최대가 10000이므로 O(N * N)으로는 100점이 불가능하다. 꿀을 가장 많이 채집할 수 있는 경우는 밑의 세 가지이다. 벌집이 가운데 어딘가에 있고, 벌이 가장 왼쪽, 오른쪽에 위치하는 경우 벌집이 가장 왼쪽에 있고, 한 벌은 가장 오른쪽, 한 벌은 가운데 어딘가에 위치하는 경우 벌집이 가장 오른쪽에 있고, 한 벌은 가장 왼쪽, 한 벌은 가운데 어딘가에 위치하는 경우 벌집이 가장 왼쪽 혹은 오른쪽에 위치하는 경우, 한 벌이 벌집과 가장 멀리있는 것이 꿀을 채집하는데 가장 유리하다(최선의 선택). 채집한 꿀을 계산할 때, 누적 합이 사용된다. 코드 #include using namespace std; int sum[100001]; int..

문제 풀이 누적 합 문제이다. O(N * N)이 되면 50점이다. O(N)의 시간복잡도로 해결해야한다. 문자열의 처음부터 시작하여 i번째까지 나온 알파벳마다 배열에 저장해둔다. i번째 문자열이 j일 경우, 이전 j가 등장한 횟수에서 + 1한 값을 배열에 저장한다. 그외에는 이전에 등장한 횟수로 저장한다. 코드 #include using namespace std; int alpha[26][200000]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); string S; cin >> S; // 문자열의 처음부터 시작하여 i번째까지 나온 알파벳을 배열에 저장 alpha[S[0] - 'a'][0]++; for (int i = 1..

문제 풀이 수학, 누적 합 문제이다. N이 1000,000이므로 완전 탐색시 O(N * N)으로 시간초과이다. (A - B) % n = ((A % n) - (B % n) + n) % n 배열의 i번째 수까지의 누적 합을 sum이라고 하자. 임의의 j번째에서 k번째 까지(j > N >> M; // 지금까지의 합인 sum // (sum - x) % M == 0인 경우에 답을 만족하므로, // ((sum % M) - (x % M) + M) % M == 0을 만족해야 한다. // 즉, sum % M == x % M인 x의 수가 answer에 추가된다. // sum % == 0인 경우에는 sum자체도 answer에 추가되야 한다. long long answer = 0; long long sum = 0; for (..

문제 풀이 정렬, 누적 합 문제이다. 각각의 컬러공의 크기 이하의 컬러공을 모두 탐색한다면 O(N * N)으로 시간초과이다. 컬러공을 한 번만 순회하여 문제를 해결해야 한다. 컬러공을 크기의 오름차순으로 정렬한다. 정렬한 컬러공을 처음부터 탐색하면서 현재 i까지의 크기의 합을 구한다. 그 합에서 지금까지 나온 공들 중에서 i번 공과 같은 색을 가진 공들을 뺀다. 그 합에서 지금까지 나온 공들 중에서 i번 공과 같은 무게를 가진 공들을 뺀다(크기 순으로 정렬되어 있으므로 i번 공보다 크기가 큰 공은 현재까지 합해지지 않았다). 이렇게 하면, i번 공과 색상과 크기가 모두 같은 공은 총 두 번 빠진다. 그러므로, 지금까지 나온 공들 중에서 i번 공과 같은 색과 같은 크기를 가진 공들은 한 번 더해줘야 올바른..