동적계획법21 [Java] 백준 1149번 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); int N = s.nextInt(); //집의 수 int dp[][] = new int[N][3]; for(int i=0;i 2020. 4. 28. [Java] 백준 1463번 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner s= new Scanner(System.in); int N = s.nextInt(); int dp[]= new int[N+1]; dp[0]=0; dp[1]=0; //초기화 //만약 N=2,3일때 1로 만드는 경우의 수는 1이다. /* N을 1로 만드는 경우의 최소 횟수는 = 1) 'N-1을 1로 만드는 최소 횟수 +1' 2) 'N/2를 1로 만.. 2020. 4. 28. [Java] 백준 2156번 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net import java.util.Scanner; public class Main { public static void main(Stri.. 2020. 4. 28. [Java] 동적 계획법 DP(Dynamic Programming) 동적 계획법 Dynamic Programming 동적 계획법은 큰 문제를 작은 문제로 나눠서 최종 문제를 해결하는 알고리즘이다. 작은 문제를 처리할 때 수행되는 답을 저장해 놓고 다음번에 필요할 때 그 값을 불러와서 처리한다. 재활용 개념이라고 이해하면 쉽다. 분할 정복과 비슷한 개념이지만 분할 정복과 동적 계획법의 차이점은 분할 정복에서의 쪼개진 작은 문제들은 중복되지 않지만 동적 계획법에서 쪼개진 문제는 서로 연관성이 있다는 점이다. 동적 계획법의 조건 1. 겹치는 부분문제 - 어떤 문제가 여러 개의 작은 문제로 쪼개질 수 있어야 한다. 2. 최적 부분구조 - 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 해결할 수 있어야 한다. 동적 계획법 구현 방식 Top-down 방식 (재귀.. 2020. 4. 27. [Java] 백준 11052번 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); //카드 개수 입력 //System.out.println("카드 개수를 입력하시오: "); int N = s.nextInt(); int cos[] = new int[N+1]; int[] .. 2020. 1. 11. [Java] 백준 2193번 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 풀이 dp[N] = N자리 수일때 가질 수 있는 이친수의 개수 dp[1] = 1 (1) dp[2] = 1 (10) dp[3] = 2 (10.. 2020. 1. 11. 이전 1 2 3 4 다음