백준 2293. 동전 1

🅰 백준 2293. 동전 1

2293번: 동전 1

✏️ 문제 풀이

• 0.5초의 시간제한과, 4MB의 메모리 제한이 있기 때문에 1차원 배열로 풀었다.
• 예제를 이용해서 설명을 하면

  ||  1  2  3  4  5  6  7  8  9  10

  1  1  1  1  1  1  1  1  1  1  1        dp[] = 1 1 1 1 1 1 1 1 1 1 

  2  0  1  1  2  2  3  3  4  4  5        dp[] = 1 2 2 3 3 4 4 5 5 6 

  5  0  0  0  0  1  2  2  3  3  4        dp[] = 1 2 2 3 4 6 6 8 8 10

• 동전 경우의수를 구할 때 이전에 선택한 동전의 경우의 수에 현재의 동전 1개만 추가하면 되므로(중복X), 이전 합계 값을 그대로 가져와서 합계를 최신화 시켜주었다.
• 이처럼 현재 index - 자신의 동전 의 차이만큼의 경우의 수 를 가져오면 되기 때문에 1차원 배열로 풀 수 있었다.

✏️ 소스코드

package dp;

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

public class Main_실버1_2293_동전1 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int coin[] = new int[n + 1];
		int dp[] = new int[k + 1];
		for (int i = 1; i <= n; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}
		dp[0] = 1; // 나눠서 떨어지는 경우 무조건 1개로 저장
		for (int i = 1; i <= n; i++) {
			for (int j = coin[i]; j <= k; j++) { // 코인 값 부터 시작
				dp[j] += dp[j - coin[i]]; // 코인을 뺀 수의 경우의수에 자기자신을 선택하면 됨
			}
		}
		System.out.println(dp[k]);
	}
}

 

✅ 후기

• 도저히 생각을 해봤는데 중복을 해결하는 방법을 생각해내지 못했다.. 많은 문제를 접해보고 내것을 만들려고 노력을 해야겠다.