study

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제해결 - dp[n][0] : 사자를 넣지 않는 경우, 모든 경우의 수를 더해야됨 - dp[n][1] : 사자를 왼쪽 우리에 넣는 경우, 바로 위쪽에 있는 경우를 제외한 모든 경우를 더함 - dp[n][2] : 사자를 오른쪽 우리에 경우, 바로 위쪽에 있는 경우를 제외한 모든 경우를 더함 import java.util.Scanner; public class B1309 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = ..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제해결 - dp 배열에 n번째 집을 각 색으로 칠하는데 최소값을 집어 넣는다 - 연속된 색을 칠하면 안되니 1일때는 2,3의 최소값 2일때는 1,3의 최소값... 이런식으로 같은 색은 제외한다 - dp[n] 에서 가장 작은 수가 답인데, 이때 나올수 있는 수중 가장 큰 값인 1000*1000으로 min을 초기화해서 가장 작은 수를 구한다 import java.util...

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 https://broship.tistory.com/219 - 백준 9095 문제와 똑같은 문제다, 다만 n의 최대값이 1000000으로 바뀌었다 - 처음 dp 배열을 1000000 크기로 생성 후 오버플로우를 방지하기 위해 모든 덧셈을 한 후 1000000009을 나눠주면 된다. import java.util.Scanner; public class Main { public static void main(String[] args) { ..

문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 - 주석참고 import java.util.Scanner; public class B2225_2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[][] dp = new int[201][201]; // k=1, 정수 1개만으로 i를 만들어야 할때 무조건 1가지 경우밖에 없음 for (int i = 1; i

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제해결 - 11일 경우 1^2 + 1^2 + 1^2..... : 11개 (j=1) dp[10] + 1^2 : (dp[10]+1) 3개 (j=2) dp[7] + 2^2 : (dp[7] + 1) 5개 (j=3) dp[2] + 3^2 : (dp[2] + 1) 3개 이 중 최소값인 3이 정답 import java.util.Scanner; public clas..

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제해결 - dp 배열을 만들어 반복문을 돌면서 i번째 까지의 연속합 중 가장 큰 값을 dp배열에 담는다 - dp 배열 중 가장 큰 값이 연속합 중 가장 큰 값이 된다 - 맨 첫번째 숫자의 연속합은 자기 자신이므로 dp[0] = arr[0]으로 초기화 해준다 - 예제 1번의 수열일때 10 -4 3 1 5 6 -35 12 21 -1 dp 배열: [10, 6, 9, 10, 15, 21, -14, 12, 3..

문제 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 문제해결 - 11053 가장 긴 증가하는 수열 문제와 똑같이 가장 긴 수열 길이를 구하고 배열 역추적을 하면 된다 - 가장 긴 배열이 max라 했을때, dp 배열 뒤에서부터 검사하면서 max와 같은 경우를 stack에 담고 max를 -1 하면 된다 - 뒤에서 부터 검사하므로 LIFO 구조인 stack을 사용한다..

문제 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 문제해결 - dp 배열을 만들어 0~N번째 까지 가장 긴 수열의 개수를 담는다 - 어떤 숫자로도 수열을 만들면 개수가 1이므로 dp는 1로 초기화 한다 - 2중 반복문을 돌면서 i번째 숫자와 0~i번째 숫자를 비교하며 가장 긴 수열의 길이를 dp에 담는다 - i번째 숫자가 j번째 숫자보다 큰 경우 여태까지 만들 수..

문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제해결 - 피보나치 수열푸는 방식과 동일함 - n의 값이 1로 들어올때 dp[2] = 1;이 성립될수 없으므로 dp 배열의 사이즈는 넉넉하게 n+2로 한다 import java.util.Scanner; public class B2193 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); i..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제해결 - dp를 2차원 배열로 만들어 1차원에는 자리수, 2차원에는 맨 오른쪽 숫자를 표현하고 값은 각각 0~9로 끝나는 계단수의 개수를 저장한다 - n이 1일경우(한자리수일 경우) 0을 제외한 1~9이기 때문에 1로 초기화 한다 - 2자리수의 끝이 5인 계단수는 1자리수인 4, 6에 +1, -1한 값인 45, 65이다 - 맨 오른쪽 숫자가 0일경우 그 전 자리수의 1에 -1한 값만 올수 있다(1->10) - 맨 오른쪽 숫자가 9일경우 그 전 자리수의 8에 +1한 값만 올수 있다(8->89) - 이 규..