백준/누적 합
-
10986 나머지 합백준/누적 합 2024. 8. 4. 16:00
예제를 가지고 설명해보면 5 31 2 3 1 2 누적합을 통해서 문제를 풀 수 있다.특히 누적합%M 값을 이용한다. i01234입력값12312누적합13679누적합%M = A[i]10010 우리는 A[i] 값을 이용하는데, 정답으로 출력할 건수를 생각해보면, 1) A[i] = 0 인 부분i = 1,2,4 인 경우이다.각각 누적합이 3,6,9인 경우로 M(=3) 으로 나누면 나머지가 0 이므로 정답이 된다. 1-1)누적합이 3인 경우 : i = 0 부터 i = 1 까지의 합,누적합이 6인 경우 : i = 0 부터 i = 2 까지의 합누적합이 9 인 경우 : i = 0 부터 i = 4 까지의 합 즉, 3가지 경우가 있다. 1-2) 다른 경우도 생각해 볼 수 있다.i = 1,4의 경우를 생각하면,A[4]..
-
2143 두 배열의 합백준/누적 합 2022. 5. 31. 22:01
1. 풀이 다른 블로그를 참고해서 풀었다. 누적 합과 두 포인터를 이용한다. 예제를 가지고 설명하겠다. 5 4 1 3 1 2 3 1 3 2 1) 누적합 A 배열에 1 3 1 2 를 입력하고, B 배열에 1 3 2를 입력한다. 그 후 sumA 리스트에 A 배열의 누적 합을 넣어준다. A[0] A[0] + A[1] A[0] + A[1] + A[2] A[0] + A[1] + A[2] + A[3] A[1] A[1] + A[2] A[1] + A[2] + A[3] A[2] A[2] + A[3] A[3] 이런 식으로 누적 합을 sumA리스트에 넣어준다. 그 후 오름차순 정렬해준다. B 배열의 누적 합도 마찬가지로 만들어준다. => sumA : 1 1 2 3 3 4 4 5 6 7 sumB : 1 2 3 4 5 6 2)..
-
15724 주지수백준/누적 합 2022. 5. 28. 14:17
1. 풀이 누적 합을 이용한다. 예제를 가지고 설명하겠다. 4 4 9 14 29 7 1 31 6 13 21 26 40 16 8 38 11 23 3 1 1 3 2 1 1 1 4 1 1 4 4 1) sum 배열 sum[i][j] = sum[i][j-1] + (i,j) 위치에 살고 있는 사람 수 로 채운다. 즉, 9 23(9+14) 52(23+29) 59(52+7) 1 32(1+31) 38(32+6) 51(38+13) 이런 식으로 채운다. sum 배열의 (1,1) 위치 값은 9 이다. 즉 sum[1][1] = 9 2) dp 배열 dp[i][j] = (1,1) 부터 (i,j) 까지의 인구수 합 => dp[i][j] = dp[i-1][j] + sum[i][j] 즉, 3) 결과 출력 주어진 직사각형 범위의 (x1,..