본문 바로가기
반응형

Prefix Sum18

백준 2559 수열 Kotlin (누적 합) 문제 출처 : https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 또 다른 예로 위와 같은 온.. 2022. 1. 30.
백준 20116 상자의 균형 Kotlin (누적 합) 문제 출처 : https://www.acmicpc.net/problem/20116 20116번: 상자의 균형 3번 박스의 중심의 x좌표는 9이며 2번 박스의 구간 (0, 20) 에 속한다. 그리고 2, 3번 박스의 중심의 x좌표는 (10+9)/2 = 9.5 이고 1번 박스의 구간 (-10, 10) 에 속하므로 균형을 이룬다. www.acmicpc.net 문제 진수에게는 총 n개의 상자가 있다. 모든 상자는 2L × 2L 크기의 정사각형 모양이고, 상자의 밀도는 균일하다. 진수는 이 상자들을 바닥에서부터 차곡차곡 쌓아올린다. 바닥은 y=0 이다. 이 상자들을 바닥에 가까이 있는 있는 상자부터 각각 1번, 2번, ..., n번 상자라고 보았을 때 i번 상자의 중심은 (xi, 2L×i - L) 이 되고, 이는.. 2022. 1. 23.
백준 10986 나머지 합 Kotlin (누적 합) 문제 출처 : https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2.. 2022. 1. 11.
백준 17425 약수의 합 Kotlin (에라토스테네스의 체, 누적 합) 문제 출처 : https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y).. 2021. 12. 29.
백준 11660 구간 합 구하기 5 Kotlin (2차원 누적 합) 문제 출처 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (3, 4)까지 .. 2021. 12. 25.
백준 21921 블로그 c++ (누적 합) 문제 출처 : https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 문제 찬솔이는 블로그를 시작한 지 벌써 N일이 지났다. 요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다. 찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다. 찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자. 입력 첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분.. 2021. 12. 21.
백준 1749 점수따먹기 Kotlin (2차원 누적 합) 문제 출처 : https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 문제 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점수 따먹기라는 게임인데 그다지 재밌어 보이지는 않는다. 동주가 개발한 게임은 이렇다. 일단 N*M 행렬을 그린 다음, 각 칸에 -10,000 이상 10,000 이하의 정수를 하나씩 쓴다. 그런 다음 그.. 2021. 12. 18.
백준 21318 피아노 체조 Kotlin (누적 합) 문제 출처 : https://www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 문제 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주하는 것이 피.. 2021. 12. 5.
백준 20438 출석체크 c++, Kotlin (누적 합) 2022-06-14추가 문제 출처 : https://www.acmicpc.net/problem/20438 20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 문제 코로나 바이러스로 인해 H 대학은 비대면 강의를 실시하고 있다. 조교를 담당하게 된 지환이는 출석체크 방식을 바꾸려고 한다. 학생들은 접속 순서대로 3번부터 N + 2번까지 입장 번호를 받게 된다. 지환이가 한 학생에게 출석 코드를 보내게 되면, 해당 학생은 본인의 입장 번호의 배수인 학생들에게 출석 코드를 보내어 해당 강의의 출석을.. 2021. 10. 23.
반응형

티스토리툴바