글 읽기 - 일반 수학이 맞나요....

shfksekdrms2 6년 전 0

저는 동적 프로그래밍으로 해결 했는데 수학으로도 풀수가 있는건가요... 후아...

import java.util.Scanner;

//2839
public class Main {
	static int minCnt=-1;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int input = sc.nextInt();
		int cnt=0;
		
		sugaMakeDelivery(input, cnt);
		if(minCnt != -1){
			System.out.println(minCnt);
		}else{
			System.out.println(-1);
		}
	}
	public static void sugaMakeDelivery(int value, int cnt){
		int input = value;
		int totalCnt=cnt;
		if(minCnt != -1){
			return;
		}
		if(value-5 >= 0){
			input = value-5;
			sugaMakeDelivery(input, totalCnt+1);
		}
		if(value-3 >= 0){
			input = value-3;
			sugaMakeDelivery(input, totalCnt+1);
		}
		
		if(input == 0){
			if(minCnt == -1){
				minCnt = cnt;
			}else{
				return;
			}
		}
	}
}

shfksekdrms2 6년 전 0

5kg 에서 근접한 수의 몫을 구한다음에 숫자를 줄여가면서 3kg짜리로 배수가 되는지 구하는 건가요??

hun3555 6년 전 1

저의 경우는 안 되는 케이스 계산해서 구해 놓고 되는 경우면 3kg을 적당히 최소개수로 빼서 5의 배수로 만들고 5로 나눴습니다

wjdtmdrbs88 6년 전 0

5 로 최대한 가져갈 수 있는 개수는 ( 전체 중량 ) / 5 입니다 그 이상은 절대 가져갈 수가 없죠.

처음에 5로 가져갈수 있는 최대 개수를 구해놓고 3으로 가져갈 수 있는 개수를 0으로 잡은 후

시뮬레이션을 돌립니다

(5로 가질 수 있는 개수)*5 + (3으로 가질 수 있는 개수) * 3 이

주어진 중량보다 크면 5로가진걸 빼보고 빼보다가 작아지면 3으로 가질 수 있는 개수를 늘려보는 식으로 해서 구하시면 됩니다.

만일, 5로 가질 수 있는 개수를 빼보다가 0 밑으로 내려가버리면 구할 수 없는 값이 됩니다

음... 저의 경우는 일단 3kg짜리를 먼저 뺐습니다. 주어진 무게를 5k+a(0<=a<5)로 표현한 뒤, a가 1이면 6kg, 2면 12kg, 3이면 3kg, 4면 9kg을 3kg로 빼냅니다. 나머지가 없으면 모두 5kg으로 나눠 주면 됩니다. 그리고 남은 무게를 5kg로 나눠 주면 됩니다. 구할 수 없는 값은 총 4개입니다. 1kg, 2kg, 4kg, 7kg입니다.

5k+1: 6kg, 11kg, 16kg, ...

5k+2: 12kg, 17kg, ...

5k+3: 3kg, 8kg, 13kg, 18kg, ...

5k+4: 9kg, 14kg, 19kg, ...

5k: 5kg, 10kg, 15kg, 20kg, ...

이렇게 배열하면 분명해지죠. 8kg부터는 모두 가능하고, 그 이하에서 안 되는 경우는 1kg, 2kg, 4kg, 7kg뿐입니다. 또한 어째서 6kg, 12kg, 3kg, 9kg을 뺐는지도 보여줄 수 있을 것이라고 생각합니다...

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

문제

문제

출처

ICPC

일반 수학이 맞나요....

shfksekdrms2 6년 전 0

jh05013 6년 전 1

shfksekdrms2 6년 전 0

hun3555 6년 전 1

wjdtmdrbs88 6년 전 0

hun3555 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말