[ 자바 ] - 동전1 , 동전2

 

 

 

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

2293번: 동전 1

 

 

일단 결과는 둘다 실패이다. 동전1은 시간초가 , 동전2는 틀린답... 반례를 찾는중이다.

동전 1과 동전2의 차이는 동전1은 경우의수를 찾는것이고 , 동전2는 최소한의 값을 찾는부분이다.

 

 

동전 1 로직을 힘들게 힘들게 짯는데 ... 재귀함수를 사용하여 완전탐색하는 로직이라 시간이너무올래걸리는듯하다

동전1을 약간 변형하여 동전2에 사용하였다. 

 

 

코드설명은

 

받은 동전을 배열에 담고 , 받은동전당 k 까지 몇개가있으면 되는지 센 후 

 

check 함수에서 배열 첫번쨰값을 꺼내서 더하고   재귀함수를 사용해서 두번째, 세번째 값도꺼낸후 더한다 마지막에 값이 k랑 같은지 체크하는 방식이다

 

ex) n=3 , k=12  동전 3개의 가치는 1,2,5 이고 , 동전을 여러반 사용하여 12가 될 경우의 수를 구하는 것이다

3 12

1

2

5

정답은 10

 

경우의수 

1 * 12 + 2*0 + 5*0

1*10 + 2*1 +5 *0

1*8 + 2*2 +5*0

1*7 + 2*1 + 5*1

1*6 + 2*3 +5*0

1*4 + 2*4 +5*0

1*2 + 2*5 +5*0

1*2 + 2*0 +5*2

1*0 + 2*1 +5*2

1*0 + 2*5 + 5*0

 

 

동전 1

 

import java.util.Scanner;

public class Main {
static int num=0;
static int n=0;
static int k=0;
public static void main(String[] args) {

Scanner sc  = new Scanner(System.in);
 n = sc.nextInt();
 k = sc.nextInt();

int[] arr = new int[n];  // 동전 가치 
int[]  mArr = new int[n];  // 최대 동전 넣을 수 있는 수 
for(int i=0;i<n;i++) {
int tmp =sc.nextInt();
arr[i]= tmp;
mArr[i]= k/tmp;
}

check(arr,mArr,0,0);

System.out.println(num);

}

static void check(int[] arr,int[] mArr,int n,int m) {
int count = m;
if(n==3) { //종료
if(count==k) {
num++;
}
return;
}

for(int i=0;i<=mArr[n];i++) {
count += arr[n]*i;
check(arr,mArr,n+1,count);
count -= arr[n]*i;
}
}

}

 

좀더 문제를 풀어보면서 다른방식을 찾아야긋다.

 

 

 

동전 2

import java.util.Scanner;

public class Main {
static int num=10000;
static int n=0;
static int k=0;
static boolean bool;
public static void main(String[] args) {

Scanner sc  = new Scanner(System.in);
 n = sc.nextInt();
 k = sc.nextInt();

int[] arr = new int[n];  // 동전 가치 
int[]  mArr = new int[n];  // 최대 동전 넣을 수 있는 수 
for(int i=0;i<n;i++) {
int tmp =sc.nextInt();
arr[i]= tmp;
mArr[i]= k/tmp;
}

check(arr,mArr,0,0,0);
if(bool) {
System.out.println(num);

}else {
System.out.println(-1);
}


}

static void check(int[] arr,int[] mArr,int n,int m,int q) {
int p =q;
int count = m;
if(n==3) { //종료
if(count==k) {
if(num>p) {
num=p;
bool=true;
}
}
return;
}

for(int i=0;i<=mArr[n];i++) {
p+=i;
count += arr[n]*i;
check(arr,mArr,n+1,count,p);
count -= arr[n]*i;
p-=i;
}
}

}