04.04 학습&숙제

썸네일 출처

04.04 학습! DP.2

---

복습

dp 6단계

1. 문제에 대한 정의
2. 부분 문제로 식별
3. 동적 테이블 정의
4. 부분문제들 간 관계 파악 => 점화식 도출
5. 동적 테이블 채우기
6. 해 도출

---

타일 채우기

하향식 접근 타일을 N번째 칸에 채웠을 때 T(N-1) 의 경우의 수가 그 경우의 수다!

---

이항 계수 구하기

이항 계수를 조합으로 바로 구할 수 있다!

조합 팩토리얼을 구하는게 귀찮으니 파스칼 삼각형 이용!

---

거스름돈 구하기

최적해를 부분 최적해를 이용하여 해결하기

kick : 상향식 vs 하향식의 차이에 대해서 생각!

---

결론

최적해, 부분문제, 중복 이 3가지 요소가 맞춰지면 dp 로 풀자

---

백준 1890번: 점프

---

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[][] map;
	static long[][] cnt;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		map = new int[n+1][n+1];
		cnt = new long[n+1][n+1];
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=n;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		cnt[1][1] = 1;
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				int count = 0;
				
				for(int r=1;r<=9;r++) {
					if(i-r>=1) {
						if(map[i-r][j] == r) {
							cnt[i][j] += cnt[i-r][j];
						}
					}
					if(j-r>=1) {
						if(map[i][j-r] == r) {
							cnt[i][j] += cnt[i][j-r];
						}
					}
				}
			}
		}
		
		System.out.println(cnt[n][n]);
		
	}
}

숙제

특강 대비 문제 풀기..