JUINTINATION

문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0부터 n까지의 정수 k개를 더해서 그 합이 n이 되는 경우의 수를 구하는 문제입니다. 이때 덧셈의 순서가 바뀐 경우는 다른 경우(1+2와 2+1은 서로 다른 경우)이며 한 개의 수를 여러 번 쓸 수도 있습니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp 배열은 임의의 수 x, y가 있을 때 x를 만들어야 할 때 더할 수 있는 남은 횟수가 y인 경우의 수를 의미합니다. decomposition 함수에서 y가 1이라면 x를 수 1개를 이용하여 만들 수 있는 경우는 x 1가지 이므로 1을 반환하고 y가 1이 ..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 여행에 필요하다고 생각하는 n개의 무게와 가치를 가지는 물건이 있을 때 최대 k만큼의 무게만을 넣을 수 있는 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제입니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp 배열은 임의의 수 x, y가 있을 때 1번부터 x번 사이에서 물건을 여러 개 골랐을 때 가방이 더..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 문자로 된 두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것의 길이를 구하는 문제입니다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK로 길이는 4입니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp 배열은 임의의 수 x, y가 있을 때 str1.charAt(0부터 x까지)와 str2.charAt(0부터 ..

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 두 전봇대 a와 b 사이에 설치된 전깃줄 중에 몇 개의 전깃줄을 없애 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제로 LIS(Longest Increasing Subsequence)를 응용하여 해결했습니다. 코드 자바 탑다운 방식을 이용한 코드입니다. poleA 배열은 전봇대 a에 설치된 전깃줄의 위치를 의미하며 arr 배열은 임의의 수 x..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 11053번과 11722번 문제에서 사용했던 LIS(Longest Increasing Subsequence)와 LDS(Longest Decreasing Subsequence)를 동시에 사용해서 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족하는 바이토닉 수열 중 가장 긴 수열의 길이를 구하는 문제입니다. 예를 들어, {10, 2..

문제 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 풀이 14002번 문제와 반대로 LDS(Longest Decreasing Subsequence)를, 즉 어떤 수열이 주어졌을 때 가장 긴 감소하는 부분 수열을 구하는 문제입니다. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10,..