Hee's Story

문제 N x M 의 직사각형이 주어지며, 각 칸에는 정수가 들어있다. 이제 Q개의 질문에 대하여 답을 해야 하며, 각각의 질문은 (a, b)부터 (c, d)까지의 직사각형에 들어있는 정수의 합을 묻는다. 예를 들어, 다음과 같이 5 x 5 의 직사각형이 주어질 때, (1, 2) 부터 (3, 3) 까지의 직사각형에 들어있는 정수의 합은 26 이다. 입력 첫 번째 줄에 N, M, Q가 주어진다. ( 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 ) 두 번째 줄부터 N x M 직사각형이 주어진다. 직사각형 안의 숫자 S는 -100이상 100이하이다. 그 후 Q개의 질문이 주어진다. 각각의 질문은 “a b c d” 로 이루어 져 있으며, 이는 (a, b) 부터 (c, d) 까지의 직사각형에 들..

문제 숫자 1, 2, 3을 이용하여 숫자 N을 만드는 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들어, N이 4일 경우에는 다음의 7가지 경우가 존재한다. 단, 경우의 수가 매우 많을 수 있으므로, 경우의 수를 1,000,007 로 나눈 나머지를 출력한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 입력 첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 출력 1, 2, 3을 이용하여 N을 만들 수 있는 경우의 수를 1,000,007 로 나눈 나머지를 출력한다. 예제 입력 4 예제 출력 7 예제 입력 200 예제 출력 290816 풀이 n 경우의 수 count[i] 1 1 1 2 1+1 2 2 3 1+1+1 1+2 2+1 3 4 4 1+1+1+1 1+1+2 ..

동적 계획법이란? - 큰 문제를 작게 최소화해서 푸는 알고리즘이다. - 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결한다. - 시간 복잡도를 줄이기 위해 공간을 늘린다. - 즉, DP는 이전 정보를 가지고 있어서 공간을 많이 사용한다. 풀이 순서 1. 구하고자 하는 큰 문제에서 작은 부분 문제를 정의한다. 2. 가장 작은 부분 문제부터 풀어 문제에 대한 점화식을 구한다. - 가장 작은 부분 문제의 답을 저장한다. - 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 구한다. 3. 문제를 해결한다. 주의할 점 - 초기화