자바 백준 1010번실버 5https://www.acmicpc.net/problem/1010     문제 보기분류: 수학, 다이나믹 프로그래밍, 조합론     코드 풀이import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 테스트 케이스의 수 T를 입력 int T = sc.nextInt(); // 각 테스트 케이스에 대해 반복 for (int t = 0; t

자바 백준 12865번골드 5https://www.acmicpc.net/problem/12865     문제 보기분류: 다이나믹 프로그래밍, 배낭 문제     코드 풀이import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 물품의 수 N과 배낭의 최대 무게 K를 입력 int N = sc.nextInt(); int K = sc.nextInt(); // 물품의 무게와 가치를 저장할 배열 생성 int[] weights = new int[N]; int[] values = new int[N];..

자바 백준 9251번 골드 5 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 보기 분류: 다이나믹 프로그래밍, 문자열 코드 풀이 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 두 문자열 입력 String str1 =..

자바 백준 9084번 골드 5 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 보기 분류: 다이나믹 프로그래밍 코드 풀이 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 테스트 케이스의 개수를 입력받음 int T = sc.nextInt(); // ..

자바 백준 10211번 실버 4 https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 문제 보기 분류: 다이나믹 프로그래밍, 브루트포스 알고리즘, 누적 합 코드 보기 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 테스..

자바 백준 9465번 실버 1 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 보기 분류: 다이나믹 프로그래밍 코드 보기 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 테스트 케이스 개수 입력 int T = sc.nextInt(); for (int t..

자바 백준 11726번 실버 3 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 보기 분류: 다이나믹 프로그래밍 문제 풀기 지속적으로 타일을 채우는 방법은 이전 타일을 채우는 방법의 연장선이기 때문에 Dynamic Programming을 이용하여 방법의 개수를 구한다. n은 최대 1000까지 주어졌으므로 1001개의 array를 지정하여 모든 답을 저장하고 n에 대한 답만 출력한다. n = 1 일때 방법의 수는 1 n = 2 일때 방법의 수는 2 이 두 초기화..

자바 백준 9625번 실버 5 https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 문제 보기 분류: 다이나믹 프로그래밍 문제 풀기 버튼을 눌렀을때 다음에 나타날 A의 개수는 이전의 B의 개수와 같다. B -> BA 버튼을 눌렀을때 다음에 나타날 B의 개수는 이전의 A와 B의 개수와 같다. A -> B, B -> BA K번째 버튼을 누를때까지 count를 저장할 k+1 개의 array를 생성한다.버튼을 한번 눌렀을때의 값을 aCount[1] = 0 과 ..

자바 백준 1463번 실버 3 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 보기 분류: 다이나믹 프로그래밍 문제 풀기 다이나믹 프로그램으로 저장할 N + 1 개 배열을 생성한다. 2 부터 N 까지 순차적으로 각 연산이 이루어질때 최소 연산의 횟수를 찾고 지속적으로 저장한다. 이는 1을 빼는 연산의 횟수를 저장하고, 만약 i 가 2 또는 3 으로 나누어 떨어지게 되면 그 횟수를 찾아 dp[i] 와 비교하여 최소값으로 다시 저장한다. N 까지 모든 경우를 확인했을 때 dp[N] 에 저장된 최소 연산 횟수를 반환하여 출력한다. 코드 보기 import ja..

자바 백준 2839번 실버 4 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 보기 분류: 수학, 다이나믹 프로그래밍, 그리디 알고리즘 문제 풀기 설탕 봉지의 개수를 가장 적게 하기 위해서는 5kg 의 개수가 가능한 최대여야 한다. 따라서 주어진 무게에서 5kg 을 나눈 몫을 최대로 두고 5kg 의 봉지를 하나씩 제거하면서 그 남의 무게가 3kg 으로 나누어 떨어지는지 확인한다. 그렇게 나누어떨어지는 시점이 최소 봉지 개수의 반환이며, 남은 무게가 ..