누적합

https://www.acmicpc.net/problem/25589시간 제한메모리 제한1초1024MB문제N*N 크기의 격자 위에 칸마다 코인이 놓여있다.푸앙이는 격자 위에 한 변의 길이가 1 이상 N이하인 정사각형 그물을 만들어 그 안의 코인을 얻을 수 있다. 하지만 그물이 포함하는 칸 개수의 제곱에 해당하는 코인을 지불해야 한다.그물은 반드시 N*N크기의 격자 안에 완전히 포함 되어야 하고, 한 번 그물을 친 칸에는 다시 그물을 칠 수 없다.푸앙이가 정확히 두 번의 그물을 쳐서 얻을 수 있는 코인의 최대 개수를 구하시오. 입력첫 번째 줄에 정수 N(2 ≤ N ≤ 400)이 주어진다.두 번째 줄부터 N개의 줄에는 칸에 놓여 있는 코인의 수가 1행부터 차례대로 주어진다. 칸에 놓여 있는 코인의 수는 10^..

시간 제한메모리 제한2초512MB문제성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다. 배열의 길이는 N이다.배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.배열에서 연속한 수가 A와 B일 때, A 예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000) 출력첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이성관이가 좋아하는 배열의 세 번째 조건을 그대로 사용하지 않고 부정을 취하는 것이..