노래부르다

2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제 분석 N이라는 숫자를 '연속'된 자연수의 합으로 표현하고, 이 조합의 개수를 구하는 문제이다. 주목해야 할 점은 3가지라고 생각한다. 1, 연속된 자연수. 2. 메모리의 크기.(32MB) 3. N의 크기 1. 연속된 자연수 - 자연수가 1개 혹은 여러 개가 되어도 연속된 자연수라면 조합에 포함이 된다. 즉, N이라는 숫자의 연속된 자연수는 최소 1개 이상이 될 것이다. 이 외의 연속된 자연수를 찾기 위해서는, 구간 합의 개념을 이용하면..

10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 분석 위 문제는 배열의 모든 조합이 M에 대해 나누어 떨어지는가에 대해 묻고있다. 처음 문제를 접했을 때, 구간 합에 대한 개념을 알고 있다면 쉽게 풀 수 있다는 생각이 드는 문제이다. 구간 합을 모르는 사람이라면, 아래 링크를 통해 공부하고 오길 바란다. 백준 11660번 구간 합 구하기5 (C++) 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ ..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 분석 문제는 2차원 배열안에서 (x1,y1) 에서 (x2, y2)의 합을 구하는 문제이다. 원소 하나하나를 더하기보다, 구간마다의 합을 더해서 연산의 속도를 최대한 빠르게 하는 것이 포인트. 즉, 구간 합에 대해 알고 있어야 하는 문제이다. 구간 합이란? 합 배열 S의 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] (A[0]부터 A[i]까지의 합) 이라고 할 때, 합 배열..

구간 합이란?연속된 숫자들의 배열에서, 원하는 구간까지의 합을 알고자 할 때 이용하는 알고리즘.ex) 1 ~ 10이 배열에 저장되어있다고 할 때, 합 배열은 1 3 6 10 ..과 같은 방식합 배열에서의 1 = 1 / 3 = 1+2 / 6 = 1+2+3 / 10 = 1+2+3+4 if) 난 3 ~ 6의 합에 대해 알고 싶은데 어떻게 해야하나요?answer) 1 ~ 6의 합에서 1 ~ 2의 합을 뺀다면, 원하는 답을 얻울 수 있어요! 공식합 배열 S의 정의S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] (A[0]부터 A[i]까지의 합) 합 배열 S를 만드는 공식S[i] = S[i-1] + A[i] (더하고자 하는 A[i]를, 이전까지의 합S[i-1]의 합) 구간 합을 ..