DP 알고리즘

Dynamic Programming
알고리즘 수업 때 배웠는데.. 머리에 남는게 없다…
재귀(recursive)만 기억난다…
피보나치 수열을 풀 때 가장 기본적으로

if(n<=1){
  return n;
}else{
  return f(n-1) + f(n-1);

이렇게 하는데
DP를 통해 for문을 돌리면

f(0) = 0;
f(1) = 1;
for(int i=2; 2<n; i++){
  f(i) = f(i-1) + f(i-2);
}
return f(n);

피보나치 수열을 풀 때 f(2) = f(1) + f(0)을 계속 반복하면
f(3)을 구할 때 이미 구한 f(2)를 그대로 쓰면 되니까 더 효율적이다.
이게 DP의 핵심!!
재귀함수라도 이미 계산한건 또하지 말자는 것이다.

백준 11053

1) 먼저 scanner로 n, A를 받는다
2) A[0], A[1] 비교해 더 큰 값을 k에 저장
3) for(i=2; i<n; i++)에서 k보다 A[i]가 더 크면 값을 k에 저장, j++

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int A[] = new int[N];
		
		int i,k,j;

		for(i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		
		if(A[0] < A[1]) {
			j = 1;
			k = A[1];
		}else {
			j = 0;
			k = A[0];
		}
		
		for(i = 2; i < N; i++) {
			if(k < A[i]) {
				k = A[i];
				j++;
			}
		}
		
		System.out.println(j);
	}

}

❌ 오답

백준 2502번

f(1) = a
f(2) = b
f(3) = a + b
f(4) = a + 2b
f(5) = 2a + 3b
f(6) = 3a + 5b
……
f(N)일 경우는 F를 피보나치 값이라 할 때
f(N) = F(N-2) * a + F(N-1) * b

피보나치 수열의 값들을 길이가 D인 배열에 저장
K = F(D-2) * a + F(D-1) * b
맞는 값이 나올 때까지 for 루프 돌리기

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int D = sc.nextInt();
		int K = sc.nextInt();
		
		int a, b, i;
		int[] F = new int[D];
		F[1] = 1;
		F[2] = 1;
		
		for(i = 3; i < D; i++) {
			F[i] = F[i-2] + F[i-1];
		}
		
		for(a = 1; a < K; a++) {
			if((K - F[D-2] * a) % F[D-1] == 0) {
				b = (K - F[D-2] * a) / F[D-1];
				System.out.println(a);
				System.out.println(b);
			}
		}
		
	}	
}

처음에 제출할 때 K를 넣어야하는데 if와 for문 안에 D를 넣어놓고 답이 안나와서 멘붕이었다…ㅎ