취미처럼

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://school.programmers.co.kr/learn/courses/30/lessons/42897 첫번째 집을 훔칠 경우 - 마지막 집을 훔칠 수 없음 두번째 집부터 훔칠 경우 - 마지막 집을 훔칠 수 있음 import java.util.*; class Solution { public int solution(int[] money) { int answer = 0; int[] dp = new int[money.length]; int[] dp2 = new int[money.length]; dp[0] = money[0]; dp[1] = money[0]; dp2[0] = 0; dp2[1] = money[1]; for(int i=2; i< money.length; i++) { dp[i] = Math..

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...