코딩테스트63 [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] 동적 계획법 DP(Dynamic Programming) 동적 계획법 Dynamic Programming 동적 계획법은 큰 문제를 작은 문제로 나눠서 최종 문제를 해결하는 알고리즘이다. 작은 문제를 처리할 때 수행되는 답을 저장해 놓고 다음번에 필요할 때 그 값을 불러와서 처리한다. 재활용 개념이라고 이해하면 쉽다. 분할 정복과 비슷한 개념이지만 분할 정복과 동적 계획법의 차이점은 분할 정복에서의 쪼개진 작은 문제들은 중복되지 않지만 동적 계획법에서 쪼개진 문제는 서로 연관성이 있다는 점이다. 동적 계획법의 조건 1. 겹치는 부분문제 - 어떤 문제가 여러 개의 작은 문제로 쪼개질 수 있어야 한다. 2. 최적 부분구조 - 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 해결할 수 있어야 한다. 동적 계획법 구현 방식 Top-down 방식 (재귀.. 2020. 4. 27. 이전 1 ··· 8 9 10 11 다음