[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} }; 위 처럼 배열을 정의하면, 값을 지정한 칸을 제외한 남은 ..
