공작소

문제 링크 : https://www.acmicpc.net/problem/11659풀이 과정구간 합 배열을 O(N) 만에 구하여 들어오는 요청을 O(1) 씩 M번 수행한다.시간 복잡도 : $ O(N) + O(M) $전체 코드 # 11659 : 구간 합 구하기 4import sysinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())arr = list(map(int, input().rstrip().split()))sums = [0]for i in range(n): sums.append(sums[-1] + arr[i])for _ in range(m): a, b = map(int, input().rstrip().split()) p..

문제 링크 : 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)까지 ..

문제 링크 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째..

>> 문제 바로가기 (https://www.acmicpc.net/problem/16507) 문제 호근이는 겁이 많아 어두운 것을 싫어한다. 호근이에게 어떤 사진을 보여주려는데 사진의 밝기가 평균 이상이 되지 않으면 일절 보려 하지 않는다. 호근이가 이 사진에서 일부분이라도 볼 수 있는 부분을 찾아주자. 위 그림은 호근이에게 보여줄 5×6 크기의 사진이며, 각 픽셀은 밝기를 나타낸다. 호근이가 사진의 일부분이라도 볼 수 있는지 알아보기 위해서는 두 점 (r1, c1)과 (r2, c2)를 꼭짓점으로 하는 직사각형의 밝기 평균을 구해야 한다. 예를 들어, 위 그림에서는 (2, 2)와 (4, 5)를 꼭짓점으로 하는 직사각형을 말한다. 호근이에게 보여줄 R×C 크기의 사진이 주어질 때, 사진의 일부분에 해당하는 ..

문제 크기 N의 1차원 양의 정수 배열로 이루어진 자벌레가 있다. 자벌레는 곤충이기 때문에 머리, 가슴, 배로 부위를 구분할 수 있다. 각 부위는 배열상에서 연속하는 구간으로 나타낼 수 있으며 배열상에서 머리는 왼쪽에, 가슴은 가운데에, 배는 오른쪽에 존재한다. 각 부위의 크기는 배열상에서 해당하는 구간의 값의 합으로 정의된다. 무지는 이 자벌레가 가슴이 배보다 크고 배가 머리보다 크다는 사실은 알고 있지만 어느 지점에서 머리 가슴 또한 가슴 배가 구분되는지 알지 못한다. 무지를 도와 구분될 수 있는 경우의 수를 구해주자. 엄밀하게는 다음 조건에 맞는 X,Y 쌍의 개수를 구해주자. 배열에 i번째 원소의 값을 A_i라 할 때 입력 첫 줄에 정수 N이 주어진다. (3 ≤ N ≤ 1 000 000) 두 번째 ..

문제 사탕을 좋아하는 아기 석환은, 집에 N개의 사탕이 들어있는 자루를 들여놓았다. 자루에는 두 가지 종류의 사탕이 있는데, 작은 사탕은 3g의 무게를 가지고, 큰 사탕은 5g의 무게를 가진다. 똑똑한 아기 석환은 자루에 있는 모든 사탕에 대해서, 그 사탕의 당도 si 를 계산해 놓았다. si 는 양의 정수로, si 가 클수록 사탕은 달콤하다. shake! 2019 대회에 참가하기 위해 짐을 싸고 있는 아기 석환은, 달콤한 사탕을 최대한 많이 담아가서 대회 도중 당분을 보충하려고 한다. 하지만, 연약한 아기 석환은 가방에 최대 wg (w그램) 의 사탕만을 담을 수 있다. 아기 석환이 이 조건을 만족하면서 사탕을 담았을 때, 담아간 사탕의 당도의 합은 최대 얼마가 될 수 있을까? 입력 첫 번째 줄에 사탕의..