목록누적 합 (10)

1일1알

백준 11441번 합 구하기 C++

https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 누적 합 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 =..
알고리즘 2023. 4. 15. 12:07
백준 12847번 꿀 아르바이트 C++

https://www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (1 ≤ n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net 정해진 구간만큼의 합을 슬라이딩 윈도우로 구하면서 최대값을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using nam..
알고리즘 2023. 3. 19. 10:06
백준 21318번 피아노 체조 C++

https://www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 누적 합 문제이다. 한가지 주의해야 할 점이 있는데, 예를 들어 전체 연주 1 ~ 10 구간의 5 부분에서 실수를 한다고 했을 때, 만약 1 ~ 5까지만 연주를 한다고 하면 5 뒤는 없기 때문에 이때는 실수를 하지 않는다. #include #include #include #include #include #include #include #include #include #include #inclu..
알고리즘 2023. 3. 14. 10:10
백준 21921번 블로그 C++

https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 누적 합, 슬라이딩 윈도우 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, x; vect..
알고리즘 2023. 2. 11. 14:06
백준 16139번 인간-컴퓨터 상호작용 C++

https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 알파벳별로 누적합을 저장해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int..
알고리즘 2022. 12. 2. 12:30
백준 17390번 이건 꼭 풀어야 해! C++

https://www.acmicpc.net/problem/17390 17390번: 이건 꼭 풀어야 해! [2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다. www.acmicpc.net 정렬 후 누적합을 구해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, q; vector v; vector accSum; int main() { ios_base::sync_wit..
알고리즘 2022. 11. 30. 10:08
이전 Prev 1 2 Next 다음