[백준] 2293 - 동전 1 (JAVA)

1. 소요시간 : 1시간 10분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 5
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/2293
8. 푼 날짜 : 2023.03.22

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 사고과정

먼저 2차원 dp테이블을 구성할 생각을 했다.
그리고
다음의 테이블을 구성했다. 하지만 dp[i][j] 가 어떤 규칙으로 만들어지는지를 30분 동안 고민해도 답을 찾지 못했다. 그래서 다른 사람의 코드를 참고하기로 했다.

그리고 여기서 하나 더 간과한 것이 메모리 제한이 4MB이고 n,k가 각각 100, 10000이니 나처럼 2차원 dp 테이블을 구성한다면 어차피 메모리 초과로 오답처리 됐을 것이라는 것.

메모리가 널널했어도 못풀었을텐데 여기서 2차로 멘탈이 나갔다.

알아야 하는 것 : 왜 이 문제가 DP 문제인가 ?

DP는 이전에 메모이제이션을 해두었던 값을 기억해 두었다가 후에 활용한다. 반복되는 계산을 막기 위해서이다.

이 문제를 만약 백트래킹으로 푼다면 TLE 가 날 것이 분명.

2원을 만드는 경우의 수, 3원을 만드는 경우의 수들은 모두 이전에 메모이제이션 해두었던 값들을 활용한다.

3. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int arr[] = new int[n + 1];
		int dp[] = new int[k + 1];
		dp[0] = 1;
		for(int i=1;i<arr.length;i++)
			arr[i]=Integer.parseInt(br.readLine());
		
		for(int i = 1 ; i <= n; i++) {
			for (int j = arr[i]; j <= k; j++) 
				dp[j] += dp[j - arr[i]];	
		}

		System.out.println(dp[k]);

	}
}

4. 결과

5. 회고

dp 유형이 부족해서
100줄 짜리 그래프 이론 문제보다 10줄짜리 dp 문제가 더 어렵다

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212