[C++] 백준 11660번: 구간 합 구하기 5
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이과정 1. 아래 표에서 \((0,0)\)부터 \((i, j)\)까지의 합은 다음 식으로 구할 수 있다. $$ S(i, j) = A(i, j) + S(i, j - 1) + S(i - 1, j - 1) - S(i - 1, j - 1)$$ 2. 아래 그림에서 초록색 칸을 모두 더하고 주황색 칸을 모두 뺀 값이라고 생각하면 된다. 3. \((r_1,c_1)\..
[C++] 백준 11053번: 가장 긴 증가하는 부분 수열
문제 바로가기 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다이나믹 프로그래밍 분류의 문제를 풀다보면 어떤 문제는 금방 풀리고, 어떤 문제는 아무리 생각해보 답이 떠오르지 않는다. 이 문제는 후자에 해당했다. 첫 풀이는 간단했다. 첫 번째 요소부터 시작해서 뒤에 이어지는 값 중 자신보다 큰 값들의 개수를 출력했다. 당현하게도 이는 정답이 아니다. 자신보다 큰 수는 맞지만, 이어지는 수 보다도 큰 수가 선택 돼야 하기 때문이다. 그..
[C++] 백준 10844번: 쉬운 계단 수
문제 바로가기 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 개요 이 문제는 혼자 골똘히 생각하다가 포기한 문제다. 결국 풀이를 봤는데, 처음에는 이해하지 못 했다. 종이에 여러 번 써보니 이해됐다. 풀이 끝 자리가 0 또는 9일 때는 다음에 붙을 수가 1과 8로 한 가지 밖에 없다. 이외의 수들은 각 2개씩 이어진다. 따라서 각 숫자로 끝나는 수의 개수를 다뤄야 한다. 즉, 단계별 0부터 9까지의 개수를 담는 2차원 배열이 필요하다. 나는 그것을 아래처럼 정의했다. long long C[100][10]{ {0, 1, 1, 1, 1, 1, 1, 1, 1, 1} }; 위 처럼 배열을 정의하면, 값을 지정한 칸을 제외한 남은 ..