누적합, 수학 문제https://www.acmicpc.net/problem/10986접근 방식이 문제는 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수(부분구간의 개수)를 구하는 것이다.부분구간의 개수를 구해야 하므로 투포인터 알고리즘을 잠깐 떠올렸으나 주어진 데이터의 앞뒤 연관성이 없기 때문에 다른 방법을 고안해냈다. 투포인터 알고리즘을 쓸 수 없는 이유1) 투포인터 알고리즘의 일반적인 사용 사례투포인터 알고리즘은 주로 다음과 같은 조건을 만족하는 경우에 사용된다.정렬된 배열: 배열이 정렬된 상태에서 특정 합을 찾는 문제.특정 조건을 만족하는 구간: 예를 들어, 구간의 길이 또는 합이 특정 조건을 만족하는 경우.단일 스캔: 한 번의 배열 스캔으로 문제를 해결할 수 있는 경우.2) 투포인터 ..

누적합, 소수 판정, 에라토스테네스의 체 문제https://www.acmicpc.net/problem/17425 문제 설명1 = 1 (1)2 = 1, 2 (3)3 = 1, 3 (4)4 = 1, 2, 4 (7)5 = 1, 5 (6)6 = 1, 2, 3, 6 (12)7 = 1, 7 (8)8 = 1, 2, 4, 8 (15)9 = 1, 3, 9 (13)10 = 1, 2, 5, 10 (18)11 = 1, 11 (12)12 = 1, 2, 3, 4, 6, 12 (28)1 2 3 4 5 6 7 8 9 10 11 12 13 141 4 8 15 21 33 41 56 69 87 99 127 입력첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며..

DP, 누적합 문제https://www.acmicpc.net/problem/2560 접근 방식 문제를 단순화해서 생각해보자.우리가 구해야하는 값은 N일째 되는 날 살아있는 짚신벌레 수(를 1000으로 나눈 나머지)이다.그러면 dp에 무슨 값을 기록해야할까 ? -> for문을 N번 돌며 dp[i]에 i일에 살아있는 짚신벌레 수를 기록하자.참조해야 하는 배열 없이, 이전 dp 배열에 기록했던 짚신벌레 수를 활용하여 현재 dp 배열의 값(현재 i일째에 살아있는 짚신벌레 수)를 구할 수 있다.dp[i]는 i일째 되는 날에 살아있는 짚신벌레의 수💡 풀이코드 (성공)import sys a, b, d, N = map(int, sys.stdin.readline().split())def sol(a, b, d, N): ..