JUINTINATION

문제 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n개의 정수로 이루어진 수열 중에서 수열에서 수를 하나 제거할 수 있을 때 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp1 배열은 임의의 수 x가 있을 때 arr[x]가 맨 오른쪽에 있을 때 수열에서 수를 하나 제거하지 않고 연속된 몇 개의 수의 합 중 가장 큰 값을 의미합니다. continous 함수..

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n개의 정수로 이루어진 수열 중에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다. 코드 자바 탑다운 방식을 이용한 코드입니다. dp 배열은 임의의 수 x가 있을 때 arr[x]가 맨 오른쪽에 있을 때 연속된 몇 개의 수의 합 중 가장 큰 값을 의미합니다. continous 함수 안에서 dp[idx]가 null이라면 coninous(idx - 1)를 재귀적으로..

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