https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이번 문제는 수열과 수열 사이의 차이는 1인 점을 이용하여 간단하게 해결했다. StringTokenizer st = new StringTokenizer(br.readLine(), " "); for(int i = 1; st.hasMoreTokens(); i++) numArr[i] = Integer.parseInt(st..
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 가장 긴 증가하는 부분 수열은 아래와 같이 구할 수 있다. for(int i = 1; i numArr[j] && D[i] numArr[j] && D[i]
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 이번 문제는 확실히 매우 간단했다. 가장 마지막에 오는 숫자를 작은 문제로, 그 앞에 오는 숫자를 큰 문제로 하면 된다. 작은 문제가 1인 경우 큰 문제가 될 수 있는 건, 길이가 i-1이면서 0으로 끝나는 수이다. dp[i][1] = dp[i-1][0]; 작은 문제가 0인 경우 큰 문제가 될 수 있는 건, 길이가 i-1이면서 0 또는 1로 끝나는 수이다. dp[i][0] = dp[i-..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이번 문제는 수와 수가 차이가 1이 나는 계단수의 개수를 구하는 문제이다. 해결법은 다음과 같이 했다. 1. 조건에 맞는 dp 배열 생성. 각 행은 자릿수를, 해당 행의 각 열엔 마지막 숫자가 0~9일때 계단 수가 될 수 있는 숫자의 개수를 저장. long[][] dp = new long[101][11]; 2. 1자리 숫자일 때의 배열 초기화와 2~100 자리의 계단수의 개수 구하기 for(int i = 1; i < dp.length; i++) { for(int j = 0; j < 10; j++) { if(i ..
https://www.acmicpc.net/problem/15991 15991번: 1, 2, 3 더하기 6 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 우선 나는 이 문제를 처음부터 풀이하기엔 너무 번거로워서 아예 접근법을 모르시겠다면 이전에 작성한 1, 2, 3 더하기 포스팅을 확인하여주시면 좋을것 같다. 지난 1, 2, 3 더하기 5 문제에선 작은 문제와 큰 문제의 작은 문제가 동일하지 않은 경우를 이용하여 연속되지 않은 수들로 구성된 식의 수를 구할 수 있었다. 이번 문제는 이전 문제를 풀고 나서, 문제를 힐끔보고 자기전에 영화를 보다가 순간 생각이 번뜩여서 풀었던 문제이다 ㅋㅋㅋㅋㅋ 이번 ..
https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 이번 문제의 조건은 연속된 숫자가 없는 식으로 n을 표현해야 한다. 그렇기 위해서 어떻게 점화식을 세워야 하는 것일까? 우선, 우리는 이전 포스팅에서 작은 문제를 마지막 수로 하여 n을 1,2,3으로 나타낼 수 있는 총 식의 개수를 구하였다. 혹시 이 방식을 모른다면 이전 포스팅을 참고해볼 것을 추천한다. 이번 문제는 수를 나타낼 때, 연속된 수를 사용해서 합을 나타내면 안된다. 그럼 어떻게 우리는 할 수 있을까? 작은 문제가 1일 때, 큰 문제의..
https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이 문제를 풀기 앞서, 아래의 문제를 풀지 않았다면 아래의 문제를 풀어보고 해당 문제를 풀어보고 오길 추천한다. https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acm..
https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 우선 카드 i개를 구매했을 때 드는 최대 지불 비용을 Dp[i]. 카드팩 i의 가격을 P[i]라고 하겠다. 문제에서 구하라고 하는 것은 카드 N개를 샀을 때의 최대 비용이므로 이를 이용하여 큰 문제와 작은 문제로 나눠보겠다. 작은 문제는 마지막에 구매한 카드팩의 개수, 큰 문제는 마지막 카드팩을 제외한 카드를 사는데 드는 총 비용이라고 나눈다. 즉, 마지막에 구매한 카드팩의 개수가 i라면, N-i개의 카..
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이 문제도 작은 문제와 큰 문제로 나누면 정말 쉽게 풀 수 있었다. 혹시나 이 글을 읽는 분들에게 도움이 될수도 있기에 말하자면, 내가 몇문제를 풀어보면서 느낀 DP의 가장 좋은 접근법은 가장 작은 문제와 나머지의 문제(큰 문제)로 나누면 정말 효과가 좋았다. 그리고 작은 문제가 더 작게 나눠진다면 당연히 그건 가장 작은 문제가 아니라서 더 작게 놔눠볼 것을 추천한다. 어쨌든 이번 문제도 가장 작은 문제와 나머지 큰 문제로 나눠 보겠다. 문제에선 1,2,3을 더한다고 하였으니 우리는 이 수가 가..
우선 이 문제를 풀기 전에 아래의 문제를 풀어보지 않았다면 해당 문제를 풀어보고 이 문제를 푸는 것을 추천한다. https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이 문제도 2 x n 타일링 문제와 완전히 동일하게 접근하면 된다. 이 문제 또한 작은 문제와 큰 문제를 마지막에 올수 있는 블록의 형태를 구해본다. 1. "2 x 1 타일"을 한개 2. "1 * 2 타일"을 높이로 두개 3. "2 * 2 타일"을 한개 위와 같이 총 3개의 경우의 수만 올수 있다. 이 때 ..
