글 읽기 - 동전1 문제 중복 제거와 관련해서 질문있습니다.

qkrgusxkr 6년 전 0

동전 1 문제 접근을,

d[i] = d[i-arr[0] + ... d[i-arr[n]으로 생각해서

for(int i=1;i<=Num;i++){

for(int j=1;j<=n;j++){

if(i>=arr[j]) d[i]+=d[i-arr[j];

} }

이렇게 풀었는데요. 중복이 있어서 답보다 크게 나오네요..

중복을 제거하는 경우의 수를 생각해봤는데, 쉽지 않아서요. 어떻게 중복을 제거하며 더할 수 있을까요??

import java.util.Scanner;

public class A2293 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int Num=sc.nextInt();
		int[] arr = new int[n+1];
		int[] d = new int[Num+1];
		
		for(int i=1;i<=n;i++) {
			arr[i]=sc.nextInt();
		}
		d[0]=1;
		for(int i=1;i<=Num;i++) {
			for(int j=1;j<=n;j++) {
				if(i-arr[j]>=0)
					d[i] += d[i-arr[j]];
			}	
		}
		System.out.println(d[Num]);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

동전1 문제 중복 제거와 관련해서 질문있습니다.

qkrgusxkr 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말