algorithm

https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 백준 2018번과 비슷하게 숫자를 변수로 지정해 푸는 문제로 두 수를 더해서 특정 숫자로 만드는 경우가 몇 갠지 묻는다. 코드를 단순 구현하듯이 쓰다가 정렬을 해야지만 숫자를 포인터로 지정할 수 있겠다 싶었다. 파이썬은 sort함수를 사용하면 오름차순으로 정렬해준다. 첫 번째 숫자를 리스트의 맨 처음, 두 번째 숫자를 맨 마지막으로 지정해 준다 합해서 만들어야 하는 숫자가..

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)을 구하고 구간을 다루는 연습을 했었다. 비록 규칙이 있는 수들이 아닐지라도 구간을 다루는 방법은 똑같으므로 떠오른다면 문제푸는데 도움이 될 것이다. 그래서 사용할 방법은 구간 합 배..