[BaekJoon] 백준 2839번 설탕배달(자바)

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

2839번: 설탕 배달

 

기본 조건을 잘못줘서 99%에서 자꾸 틀리길래 애먹었다.

5랑 같거나 클 때라고 해야하는데 > 으로 해버려서 어디서 오류나는건지 한참찾았다

.

 

 

일단 DP를 사용해서 풀었다. for문이 더 빠를거같은데 생각하기 귀찮아서  처음 생각한게 재귀니까 재귀로 풀었다.

 

내가 세운 점화식은

 

d[n] = Min(d[n-5], d[n-3]) + 1 이다.

 

여기서 설탕이 나눠지지 않을 때와 5로 나누어 떨어졌을 때 무조건 최소가 된다는 점을 추가해서 풀었다.

사실 설탕을 5Kg 자루에 담을 수 있을 때 무조건 최소가 된다. 그래서 d[n-5]가 -1 가 나오지 않는 이상 n-3은 굳이 할 필요가 없다.

 

나중에 시간나면 for문으로도 풀어봐야겠다.

import java.io.*;

public class Main {
	static int[] d;
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			
			int n = Integer.parseInt(br.readLine());
			d = new int[n+1];
			
			d[3] = 1;
			if(n >= 5)
				d[5] = 1;

			if(n % 5 == 0)
				System.out.println(n/5);
			else
				System.out.println(func(n));
			
			
		}catch(IOException e) {
			
		}
	}
	
	static public int func(int n) {
		if(n < 3)
			return -1;

		if(d[n] == 0) {
			int result = func(n-5);
			
			if(result > 0) {
				d[n] = result + 1;
			}
			
			else {
				int result2 = func(n-3);
				
				if(result2 > 0) 
					d[n] = result2+1;			
				else 
					d[n]=-1;			
			}
			
		}
	
		return d[n];
	}
}