전체 글

https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한www.acmicpc.net모든 경우의 수에 대해서 해당하는 가짓수를 찾을 때마다 연산을 다시 한다면 상당히 비효율적일 것이다. 따라서 이전에 했던 연산(합)을 그대로 이어나가는 방법을 이용하여 풀었다.아이디어는 그리 복잡하진 않다.  맨 처음 합(total)을 1로 저장하고 start와 end로 구간을 정한다. 그리고 start부터 end까지의 합을 total에 저장하는데 total 이면 end를 뒤로 ..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제를 딱 보자마자 드는 생각은 모든 경우의 수를 m으로 나누고 나누어 떨어지면 answer += 1 하는 생각이 들었지만 당연히 이렇게 하면 시간초과가 뜰게 뻔하다. 그래서 고등학교 때 수학에서 배웠던 것들을 사용하여 풀었다. 고등학교 때 수열을 하면서 부분합을 배웠었고, 어떤 두 수를 나누었을 때 나머지끼리 빼서 0이 되면 원래 나누기 전의 수끼..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 이 문제는 백준 11659번의 상위 문제로 구간합의 성질을 2차원 배열에서 이용한 문제다. 문제를 처음 봤을때 잘 이해가 안갔었는데 밑의 표에서 (2,2)부터 (3,3)까지의 합을 구하라고 한다면 (2,2), (2,3), (2,4), (3,1), (3,2). (3,3) 으로 모두 더하는 문제로 잘못 이해했다. (이래서 예시를 잘 봐야하는....) 하이튼 ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 물론 입력받는 숫자들을 리스트에 다 넣어서 구간을 다 더하는 방법도 있겠지만, 구간 합을 구하는 성질을 이용하면 효율적으로 문제를 해결할 수 있다. 고등학교 시절 수열을 배울 때 수열의 합(S)을 구하고 구간을 다루는 연습을 했었다. 비록 규칙이 있는 수들이 아닐지라도 구간을 다루는 방법은 똑같으므로 떠오른다면 문제푸는데 도움이 될 것이다. 그래서 사용할 방법은 구간 합 배..