MingyuPark

문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 아이디어 누적합을 이용해야 한다. 주어진 표에서 각 좌표별로 누적합을 계산한 뒤에 내가 구하고자 하는 좌표의 누적합을 구하면 된다. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 위의 표에서 각 위치별 누적합을 구해보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 우선 첫 번째로 (1, 2)의 2에 (1, 1)의 1을 더해주..

문제 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 아이디어1 - DP Pypy3에서는 성공했고, Python에서는 시간 초과가 발생한 방법이다. 아이디어는 다음과 같다. 자연수 n에 대하여, n을 최소 개수의 제곱수 합으로 표현했을 때 그 개수를 f(n)이라고 하자. 이 때, n보다 작은 모든 제곱수 k에 대해 m = n - k 라고 하면, f(n)은 f(m)의 최솟값 + 1이 된다. (제곱수를 더한다는 ..