일단 시작해보는 블로그

DP가 아닌 Greedy를 떠올려야 하는 이유 Ai는 Ai-1의 배수이므로, 모든 경우의 수를 전부 다 해보는 dp로 한다면, 비효율적이다. 따라서 그리디로 구현해야한다. 코드 package greedy; import java.util.Scanner; // 문제 : 동전 0 // 예제1 : 동전 10(N)종류로 4200(K)원을 만들 때, 동전개수의 최솟값구하기 public class backjoon_11047 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 1. 입력 int N = sc.nextInt(); // N : 동전종류의 수 int K = sc.nextInt(); // K : 동전의 합 //동전의..

** dp문제라고 판단했을 때, 가장 먼저 해야하는 것 : 메모이제이션을 위한 배열 d 정의하기. ** d[i] 정의 i계단까지 왔을 때 문제에 만족하는 조건에 만족하며, 얻을 수 있는 최대 점수. 문제에 만족하는 조건 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 한 계단 전에서 왔다면 그 이전에는 두 계단 이전에서 왔어야한다. 마지막 도착 계단은 반드시 밟아야 한다. -> d[N]을 구하면 된다. 경우의 수 생각해보기 i의 입장에서 생각해 봤을 때 다음과 같다. 1. i-1을 밟고 온 경우 d[i] = d[i-3] + ..

스티커는 2행 n열로 주어진다. 하나를 떼면 왼쪽, 오른쪽, 위, 아래를 연속으로 뗄 수 없다. 따라서 왼쪽부터 오른쪽으로 스티커를 뗄 수 있으면서 그 값이 최댓값인 것을 경우의 수 중에서 고를 것이다. 생각 각각 열마다 3가지 경우의 수를 둘 것이기 때문에 이렇게 할당했다. int[][] d = new int[n+1][3]; d[i][0] = i열에서 하나도 안뗐을 때, 그전부터 이 상황((k=1; k '그 전부터 이 상황까지'의 부분이 dp가 적용되어야할 부분. d[i][1] = i열에서 위에꺼만 뗐을 때, 그전부터 이 상황까지 더한 값. d[i][2] = i열에서 아래꺼만 뗐을 때, 그전부터 이 상황까지 더한 값. -> 결국 마지막 열에서 d[n][0], d[n][1], d[n][2]의 최댓값을 구..

전형적인 dp문제 중, 최댓값(Math.max) 구하는 것. bottom-up, 저장해놓은 것보다 큰 값이면 ok아니면 새로 계산한 값 넣기의 종류 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 상담 가능 일자 int[] T = new int[N+10]; // 상담을 완료하는데 걸리는 일자 int[] P = new int[N+10]; // 상담을 했을 때 받을 수 있는 돈 int[] dp = new int[N+10];// dp memoization을 위한 배열 //1부터 N까지 입력받는다..