[백준]2293번 동전1 ( 나중에 다시 풀어볼 것 )
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다.
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
- n 가지 종류의 동전을 사용해서 k 를 만드는 것.
종류는 최대 100가지
합인 k 는 최대 1만.
동전의 가치는 10만 이하의 자연수
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. —> 따라서 각 경우에 대한 동전의 개수에 따라 경우에 대한 유일성을 부여해야할 듯 하다.
문제풀이
오랜만에 푸니 정말 안 풀린다.
- 각 가치에 대한 동전 개수의 경우의 수로 풀면, 각각 2가지 경우가 있다고만 해도 2^ 100 이 된다.
개수로 풀려고만 생각하니 도무지 생각이 안난다.
- 금액으로 접근해 볼 수 없을까????
다른 사람 풀이를 보았다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;
public class Main {
public static int n ;
public static int k ;
// 연산의 수 : 최대 10000 x 100 => 100만
public static int[] dp = new int[10001];
public static int[] c = new int[101]; // 코인의 가치
// 이 코드는 무시 ( 템플릿처럼 사용중인 입출력 코드 _제네릭,함수형인터페이스 연습용 )
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static Parser<Integer> parser = new Parser<Integer>(str -> Integer.parseInt(str));
static class Parser<T>{
Function<String, T> func;
public Parser(Function<String, T> func) {
this.func = func;
}
public T parseToNumeric(String str){
return func.apply(str);
}
}
// ============================
public static void setUp() throws IOException {
st = new StringTokenizer(br.readLine());
n = parser.parseToNumeric(st.nextToken());
k = parser.parseToNumeric(st.nextToken());
for(int i =0;i<n;i++){
c[i] = parser.parseToNumeric(br.readLine());
}
dp[0] =1 ;
}
public static int solve(){
// coin 은 index 0 부터 들어가 있음
for(int i =0 ; i<n;i++) {
// dp 는 만들어야 하는 가치를 index 로 담는 것으로 하기에 1 ~ k 까지 돌아갈 것임
// 이 때, 조금이라도 연산을 줄이기 위해서는, 현재 코인의 가치보다 작은 경우는 dp[x] 에 추가되는 경우의 수가 없기 때문ㅇ
// c[i] 부터 시작하는 것으로 할 수 있다.
for(int x = c[i]; x <= k; x++){
dp[x] += dp[x-c[i]];
}
}
return dp[k];
}
public static void main(String[] args) throws IOException{
setUp();
System.out.println(solve());
}
}
Author And Source
이 문제에 관하여([백준]2293번 동전1 ( 나중에 다시 풀어볼 것 )), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/백준2293번-동전1-나중에-다시-풀어볼-것저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)