Dev.baelanche

이중 루프로 인덱스를 비교한다. i 10 30 10 20 20 10 j 10 30 10 20 20 10 dp 1 1 2 2 다음을 만족할때 수열의 길이가 1 증가한다. 1. i 가 j 보다 작을 때 2. dp[i] 보다 dp[j] + 1 이 클 때 2번 조건을 만족하지 않으면 앞의 인덱스 중 자신보다 큰 수가 있으면 길이가 무조건 1 증가한다. 수열의 길이는 최소 1이므로 dp 배열의 초기값은 1이다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i

입력이 4 1 5 6 7 일때 카드팩은 총 4장을 구매하고, 왼쪽부터 1카드팩을 사려면 1원이 들고 카드 갯수는 1장, 2카드팩을 사려면 5원이 들고 카드 갯수는 2장, 3카드팩을 사려면 6원이 들고 카드 갯수는 3장, 4카드팩을 사려면 7원이 들고 카드 갯수는 4장 이라는 뜻이다. 즉 4번째 카드팩을 구매하면 민규가 총 4장을 사기로 했으므로 1개밖에 못사고 7원이 든다. dp 배열을 만들어서 dp[n] 에 카드를 n장 샀을때 드는 최대값을 기록하는 방식으로 풀것이다. dp 배열과 연산할 배열 pack[] 를 만들고 카드를 n장 살때 드는 비용을 기록한다. (위의 예로 들면 1,5,6,7) 점화식을 구해보자. (편의상 dp[0]=0, card[0]=0 으로 했다) dp[1] = pack[1]; dp[2..

경우의 수를 구해보면 f(n) = 2(fn-2) + (f-1) 이다. 동적계획법으로 풀면 된다. public static int[] dp; public static int f(int n) { if(n == 0) {dp[0] = 0; return 0;} if(n == 1) {dp[1] = 1; return 1;} if(n == 2) {dp[2] = 3; return 3;} if(n == 3) {dp[3] = 5; return 5;} if(dp[n] != -1) return dp[n]; int result = 2*(f(n-2)%10007) + f(n-1)%10007; dp[n] = result; return result; } public static void main(String[] args) { Scann..

n의 증가에 따른 방법의 수를 구해보면 피보나치 수열이다. public static int dp[]; public static int f(int n) { if(n == 0) {dp[0] = 0; return 0;} if(n == 1) {dp[1] = 1; return 1;} if(n == 2) {dp[2] = 2; return 2;} if(dp[n] != -1) return dp[n]; int result = f(n-2)%10007 + f(n-1)%10007; dp[n] = result; return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = ..

n 의 길이에 따라 만들 수 있는 이진수열의 수를 구해보면 피보나치 수열과 같다. 1. 동적계획법을 이용하여 배열을 채운다. 2. (A+B)%M = (A%M+B%M)%M 을 이용한다. public static int f(int n) { if(n == 0) {dp[0] = 0; return 0;} if(n == 1) {dp[1] = 1; return 1;} if(n == 2) {dp[2] = 2; return 2;} if(dp[n] != -1) return dp[n]; int result = f(n-2)%15746 + f(n-1)%15746; dp[n] = result; return result; } public static void main(String[] args) { Scanner sc = new S..

n자리 이친수의 개수를 세어보면 피보나치 수열이란 것을 알 수 있다. 1. n의 범위가 90 까지이므로 자료형을 long 으로 선언해야 한다. public static long pinary(int n) { if(n == 0) {dp[0] = 0; return 0;} if(n == 1) {dp[1] = 1; return 1;} if(dp[n] != -1) return dp[n]; long result = pinary(n-2) + pinary(n-1); dp[n] = result; return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new lo..

피보나치수열을 계산하는 함수 f(n) 을 수행했을때 호출되는 f(0), f(1) 의 개수를 정리한 표이다. n f(0) f(1) 2 1 1 3 1 2 4 2 3 5 3 5 6 5 8 7 8 13 8 13 21 n=0, n=1 일때는 규칙성이 없어서 제외했다. 위 표대로 입력이 n 일때 f(n-1), f(n)을 출력해주면 된다. public static final int MAX = 41; public static int dp[] = new int[MAX]; public static int fibonacci(int n) { if(n==0) {dp[0] = 0; return 0;} if(n==1) {dp[1] = 1; return 1;} if(dp[n] != -1) return dp[n]; int result..

주어진 수 n이 3의 배수이면 나누기 3, 2의 배수이면 나누기 2, 그 외 일때는 1을 뺀다. 한번 연산을 수행했을때마다 /3, /2, -1 중에서 가장 1이 빨리 될 경우를 찾아서 연산한다. 제한시간이 2초이므로 메모이제이션 기법을 사용하였다. 1. 동적배열을 만들어 나올 수 없는 수로 초기화 한 후, 각 수 마다 최선의 횟수를 배열에 담는다. 2. n 이 1일때는 예외처리한다. 3. n 이 1일때 0 을 리턴하는 것으로 처리하였으므로 나머지 경우엔 연산을 +1 한다. public static ArrayList dp = new ArrayList(); public static int makeOne(int n) { if(n == 1) return 0; if(dp.get(n) != -1) return dp..