취미처럼

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

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 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)); StringBuilder sb = new StringBuilder();..

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 arr 10 20 10 30 20 50 dp 1 2 1 3 1 4 max = 4 max값을 역순으로 뽑아서 해당 arr 값을 출력 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws ..

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 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1 2 3 4 5 6 7 0 10 100 1000 1010 10000 10010 10100 100000 100010 100100 101000 101010 1000000 1000010 1000100 1001000 1001010 1010000 1010010 1010100 1 1 101 1001 10001 10101 100001 100101 101001 1000001 1000101 10010..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 계단 수 : +1, -1 N번째 자릿수의 개념 ex ) 54321 첫번째 자릿수 : 1 두번째 자릿수 : 2 ... 다섯번째 자릿수 : 5 N번째 자릿수의 값이 0인 경우 : 1만 가능 N번째 자릿수의 값이 9인 경우 : 8만 가능 그 외 1~ 8은 +1, -1가능 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { long mod = 1000000000; ..