백준 알고리즘 기초강의 3 - 2

오늘한것 dp 문제풀이

// 123 더하기
import java.lang.reflect.Array;
import java.util.*;

public class Main{
	static int[] _dp = new int[12];

	public static int dp(int n){
		if (n < 0) return 0;
		if (_dp[n] != 0) return _dp[n];
		_dp[n] = dp(n - 1) + dp(n - 2) + dp(n- 3);
		return _dp[n];
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		_dp[1] = 1;
		_dp[2] = 2;
		_dp[3] = 4;
		for (int i = 0 ; i < T ; i++)
			System.out.println(dp(sc.nextInt()));
	}
}

//2n 타일링
import java.util.*;

public class Main{
	static int[] _dp = new int[1001];

	public static int dp(int i){
		if (i <= 2) return i;
		if (_dp[i] != 0 ) return _dp[i];
		_dp[i] = (dp(i - 1) + dp(i - 2)) % 10007;
		return _dp[i];
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		System.out.println(dp(sc.nextInt()));
	}
}

 

- 1로 만들기

 3으로 나누고 2로 나누고 1로 뺼때 언제 가장 짧은 경로로 1로 만들수 있는지를 구하는 문제

 dp[n] = min(dp[n-1] + 1, dp[n/3] +1, dp[n/2] + 1) 로 구하면 된다!!

나는 바텀업방식으로만 풀어왔었는데 오늘 문제풀이를 통해서 탑다운 방식도 알게 되었다

탑다운 방식에서는 일단 초기화를 조건이 없는 dp[n-1] + 1로 한다음

n % 2 == 0 이라면 tmp = dp[n/2] + 1 을

n % 3 == 0 이라면 tmp = dp[n/3] + 1 과 비교를 해서 최솟값으로 갱신을 해주면 된다

 

- 2n타일링

아주 아주 유명한 문제 2n 타일링

마지막 타일이 세로 하나인 경우와 가로 두개인 경우 두가지를 나누어서 생각을 하면 된다

 

- 123 더하기

마지막에 1 더할건지 2더할건지 3더할건지 그걸통해서 n을 123으로 표현가능하다

2n타일링이랑 비슷비슷한 문제다

 

-붕어빵 판매하기

몇개의 붕어빵을 몇개단위로 나눠서 팔아야 돈을 가장 많이 버는지 물어보는 문제이다

가장 마지막 사람에게 몇개를 팔건지를 기준으로 하여 dp 를 짜면 된다고 한다

제대로 이해가 안된듯해서 직접 문제를 풀어보도록 하자

시간복잡도는 하여튼 O(n^2) 나온다고 한다