codejcd 기술 블로그

import java.util.Arrays;
import java.util.Scanner;

public class TestDemo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        int[] arr = new int[N+1];
        int[] dp = new int[N+1];
        
        for (int i=0; i<N; i++) {
        	arr[i] = scanner.nextInt();
        }
        
        // 10, 20, 10, 30, 20, 50 
        // 10, 20, 10, 25, 20, 43
        
        dp[0] = 1;
        for (int i=1; i<N; i++) {
        	dp[i] = 1;
        	for (int j=0; j<i; j++) {
        		if(arr[i] > arr[j] && dp[j]+1 > dp[i]) {
        			dp[i] = dp[j] + 1;
        		}
        	}
        }
        Arrays.sort(dp);
        System.out.println(dp[N]);

       // OptionalInt ans = Arrays.stream(dp).max();
       // System.out.println(ans.getAsInt());
        
        scanner.close();
    }
}

문제

https://www.acmicpc.net/problem/2579

분석/설계

다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

dp[n] = Math.max(dp[n-3] + arr[n-1], dp[n-2]) + arr[n]

dp[1], dp[2], dp[3] 같은 예외 사항들은 직접 식을 정의해주고 처리했습니다.

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        int[] arr = new int[301];
        int[] dp = new int[301];
        for (int i = 1; i <= N; i++) {
        	arr[i] = scanner.nextInt();
        }
        	
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        dp[3] = Math.max(arr[1], arr[2]) + arr[3];

        for (int n = 4; n <= N; n++) {
            dp[n] = Math.max(dp[n - 3] + arr[n - 1], dp[n - 2]) + arr[n];
        }

        System.out.println(dp[N]);
        scanner.close();
    }
}

정리

바텀업이 익숙해서인지 탑다운으로는 풀이를 잘 안하게됩니다.

탑다운으로 푸는 방식들이 많이 있으니 혹시 안풀릴 경우 검색해보시거나 아래 링크를 참고하면 도움이됩니다.

다이나믹은 바텀업의 경우 예시를 들어놓고 점화식으로 정리할경우 매우 빠르게 풀수있습니다.

익숙해지려면 많이 문제 유형을 만나보고 점화식을 정의할수 있게 고민해야 봐야할 것 같습니다.

참고

https://www.acmicpc.net/problem/2579

https://st-lab.tistory.com/132

문제

https://www.acmicpc.net/problem/1149

분석/설계

입력 숫자의 범위가 2~1000 이므로 다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

dp[N][0] = min( dp[N-1][1], dp[N-1][2] ) + dp[N][0]

dp[N][1] = min( dp[N-1][0], dp[N-1][2] ) + dp[N][1]

dp[N][2] = min( dp[N-1][0], dp[N-1][1] ) + dp[N][2]

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int arr[][] = new int[N+1][3];
        int dp[][] = new int[N+1][3];

        for (int i=1; i<=N; i++) {
            for (int j=0; j<3; j++) {
                arr[i][j] = scanner.nextInt(); 
            }
        }

        for (int i=1; i<=N; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
        }

        System.out.println(Math.min(Math.min(dp[N][0], dp[N][1]), dp[N][2]));
        scanner.close();
    }
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고, 문제만 보고 점화식이 잘 정의가 안되면

예시를 여러 개 만들고 패턴을 찾아내어 점화식을 만들고 알고리즘을 적용하여 코드를 작성하면 

수월합니다.

참고

https://www.acmicpc.net/problem/1149

문제

https://www.acmicpc.net/problem/9095

분석/설계

입력 숫자의 범위가 1~11이지만 다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

N이 1, 2, 3 의 경우 점화식 적용할 경우 index가 음수 값이거나 0이기 때문에

따로 정의 해줬습니다.

dp[i] = d[i-1] + d[i-2] + d[i-3]

구현 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		int N[] = new int[T];
		int dp[] = new int[11];
		
		for(int i=0; i<T; i++) {
			N[i] = scanner.nextInt();
		}
		
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		
		for(int i=0; i<N.length; i++) {
			for(int j=3; j<N[i]+1; j++) {
				dp[j] = dp[j-1] + dp[j-2] + dp[j-3];
			}	
		}
		
		for(int i=0; i<N.length; i++) {
			System.out.println(dp[N[i]]);
		}

		scanner.close();
	}
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고, 문제만 보고 점화식이 잘 정의가 안되면

예시를 여러 개 만들고 패턴을 찾아내어 점화식을 만들고 알고리즘을 적용하여 코드를 작성하면 

수월합니다.

참고

https://www.acmicpc.net/problem/9095

문제

https://www.acmicpc.net/problem/2839

분석/설계

입력 숫자의 범위가 3~5000 이기때문에 다이나믹 프로그래밍으로 풀지 않고

그리디 알고리즘으로 푸는 방법도 있을 것 같습니다.

하지만 다이나믹을 프로그래밍 사용하여 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

4, 7 같은 경우 3이나 5로 정확히 나눠서 떨어지지 않기때문에 문제의 조건대로 -1을 출력해야 하므로

이에 대한 예외 처리를 주의해야합니다.

dp[i] = min(d[i-3], d[i-5]) + 1 

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int dp[] = new int[N+1];

        dp[3] = 1;
        if(N == 4) {
            System.out.println(-1); 
            return;
        }
        if(N>4) dp[5] = 1;	

        for(int i=6; i<dp.length; i++) {
            if (i % 5 == 0) {
                dp[i] = dp[i-5] + 1;
            } else if (i % 3 == 0) {
                dp[i] = dp[i-3] + 1;
            } else {
                if (dp[i-3] != 0 && dp[i-5] != 0) {
                    dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
                } else {
                    dp[i] = -1;
                }
            }
        }

       System.out.println(dp[N]);
       sc.close();
    }
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고

편한 풀이 방식을 적용하면 될 것 같습니다.

참고

https://www.acmicpc.net/problem/2839

문제

https://www.acmicpc.net/problem/1463

분석/설계

입력 숫자의 범위가 2~10의 6제곱이기때문에 입력 범위가 크고

이렇게 입력 범위가 큰 경우 완전 탐색 알고리즘을 쓰면 항상 효율성에서 걸리는 문제들이 많았습니다.

다이나믹 프로그래밍을 적용하면 복잡도 면에서 걸리지 않을 수있다고 판단했고 이를 적용했습니다.

보통 다이나믹 프로그래밍은 점화식을 이용하면 쉽게 풀리는 경향이 있습니다.

dp[i] = min(d[i-1], d[i//2], d[i//3]) + 1 

구현 코드

import java.util.Scanner;

public class Main {
	
	static int dp[] = new int[10000001]; // 1을 만들기 위한 최소 연산 사용 횟수
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int X = scanner.nextInt();
		
		for(int i=2; i<X+1; i++) {
			dp[i] = dp[i-1] + 1;
			
			if(i % 2 == 0) {
				dp[i] = Math.min(dp[i], dp[i/2] + 1);
			}
			
			if(i % 3 == 0) {
				dp[i] = Math.min(dp[i], dp[i/3] + 1);
			}	
		}
		
		System.out.println(dp[X]);
		scanner.close();
	}
}

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고

탑다운로도 풀이한 분들이 많이 있습니다.

편한 풀이 방식을 적용하면 될 것 같습니다.

참고

https://www.acmicpc.net/problem/1463