취미처럼

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(Syst..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 점화식 : dp[i] = dp[i-1] + arr[i] import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 다음 줄과 현재 줄의 최대값을 비교하여 갱신한 후에 다음줄에 그에 해당하는 배열값을 더함 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int ..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 인덱스 신경쓸 것 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N+1]; int[] dp = ne..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long[][] dp = new long[N+1][..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp[n][0] :사자를 넣지 않은 경우 => 모든 경우의 수 dp[n][1] : 사자를 왼쪽 우리에 넣는 경우 :=> 한 줄 위의 오른쪽 우리 사자 => dp[n-1][2] dp[n][2] : 사자를 오른쪽 우리에 넣는 경우 => 한 줄 위의 왼쪽 우리 사자 => dp[n-1][1] import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanne..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net i번째 집이 빨강일 때, i - 1번째 집이 초록이거나 파랑인 경우의 최소값과 빨강값을 더한다. 0 : 빨강, 1: 초록, 2: 파랑 dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + r dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + g dp[i][2] = Math.min(dp[i-1][0], dp[i-1][..

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 정수 N 경우의 수 개수 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 1+2+1 2+1+1 2+2 1+3 3+1 7 4 + 2 + 1 dp[3] + dp[2] + dp[1] 5 1+1+1+1+1 1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+1 1+1+3 1+3+1 3+1+1 1+2+2 2+1+2 2+2+1 2+3 3+2 13 7 + 4 + 2 dp[4] + dp[3] + dp[2] 점화식 :..

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = 6, K = 4 일 때 경우의 수 0 + 6 3번 더해서 0일 때 1 + 5 3번 더해서 1일 때 2 + 4 3번 더해서 2일 때 3 + 3 3번 더해서 3일 때 4 + 2 3번 더해서 4일 때 5 + 1 3번 더해서 5일 때 6 + 0 3번 더해서 6일 때 dp[4][6] = dp[3][0] + dp[3][1] + dp[3][2] + dp[3][3] + dp[3][4] + dp[3][5] + dp[3][6] 점화식 : dp[K][N] = dp[K-1][N] import java.util.*; import java...

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net dp[ 1 ] 1² 1 dp[ 2 ] 1² + 1² 2 dp[ 3 ] 1² + 1² + 1² 3 dp[ 4 ] 2² 1 dp[ 5 ] 2² + 1² [5 - 2²] = 1 dp[1] + 1 2 dp[ 6 ] 2² + 1² + 1² [6 - 2²] = 2 dp[2] + 1 3 dp[ 7 ] 2² + 1² + 1² + 1² [7 - 2²] = 3 dp[3] + ..