99클럽 코테 스터디 30일차 TIL : Dynamic Programming(백준- 상자넣기)

 

 

🔎 문제

 

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

 

 

 

 

 

---

💡 풀이

- 

 

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

public class Main {
	
	public static Long[] arr= new Long[100];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb= new StringBuilder();
		int T= Integer.parseInt(br.readLine());
		
		for(int i=0;i<T;i++) {
			int n= Integer.parseInt(br.readLine());
			sb.append(p(n)+"\n");
		}

		System.out.println(sb);
	}

	private static Long p(int n) {
		if(n>=1&&n<=3) {
			return 1L;
		}else if(n>=4&&n<=5) {
			return 2L;
		}else if(arr[n-1]==null){
			arr[n-1]= p(n-1)+p(n-5);
		}
		
		return arr[n-1];
	}

}

 

 

 

📌 오늘의 회고

 

다이나믹 프로그래밍(Dynamic Programming, DP)

: 복잡한 문제를 단순한 하위 문제로 나누고, 각 하위 문제의 결과를 저장하여 동일한 하위 문제를 반복적으로 계산하지 않도록 하는 알고리즘 설계 기법

- 일반적으로 중복된 계산과 부분 문제의 최적 부분 구조를 활용

1. 최적 부분 구조 (Optimal Substructure)
   문제의 최적 해결책이 하위 문제들의 최적 해결책으로 구성될 수 있는 성질
   예: 피보나치 수열에서 F(n) = F(n-1) + F(n-2)
2. 중복되는 하위 문제 (Overlapping Subproblems)
   동일한 하위 문제가 여러 번 반복해서 계산되는 경우를 의미한다. 이 경우, 중간 계산 결과를 저장하면 효율성을 높일 수 있다.
   예: 재귀적으로 피보나치 수를 계산할 때, 동일한 계산이 여러 번 발생.
3. 메모이제이션 (Memoization)
   하향식(Top-Down) 접근 방식으로, 이미 계산한 하위 문제의 결과를 메모리(배열 등)에 저장하여 중복 계산을 방지한다.
4. 타뷸레이션 (Tabulation)
   상향식(Bottom-Up) 접근 방식으로, 작은 문제부터 차례대로 풀어나가며 결과를 저장해 큰 문제를 해결한다.