[백준] 2839 - 설탕배달 (Java)

[백준] 2839 - 설탕배달 (Java)

문제

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

풀이/후기

dp로 풀기 위해 점화식을 고민하여 풀었는데 오답이 나왔다.

			if (i % 3 == 0) {
				d[i] = d[3] * i/3;
			} 
			if (i % 5 == 0) {
				d[i] = Math.min(d[i], d[5] * i/5);
			}
			if ((i-3) % 5 == 0) {
				d[i] = d[i-3] + 1;
			}
			if ((i-5) % 3 == 0) {
				d[i] = d[i-5] + 1;
			}

테스트케이스 입력 시에도 다 정답이고 내 이론상 틀린게 없었는데

검색을 해보니 이런 표가 있었다

 

하나씩 비교를 해보니까 16에서 걸렸다.

내가 푼대로 하면 16은 5를 빼도 3의 배수가 아니니 조건을 타지 않기 때문.

근데 오히려 해결법은 간단했다.

			if (i % 5 == 0) {
				d[i] = d[i - 5] + 1;
			} else if (i % 3 == 0) {
				d[i] = d[i - 3] + 1;
			} else {
				if (d[i - 3] != 0 && d[i - 5] != 0) {
					d[i] = Math.min(d[i - 3], d[i - 5]) + 1;
				}
			}

이렇게하면 코드도 깔끔해지고 원하는 결과를 얻을 수 있다.

최소의 개수니까 일단 큰 수로 나누는게 효율적이니 5로 먼저 나눠주고

5, 3 배수가 아닌 경우를 따져주면 된다.

코드

package DynamicProgramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Problem2839 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] d = new int [N+1];
		
		if (N >= 3) {
			d[3] = 1;
		} 
		if (N >= 5) {
			d[5] = 1;
		}
		
		for (int i=6; i<N+1; i++) {
			if (i % 5 == 0) {
				d[i] = d[i - 5] + 1;
			} else if (i % 3 == 0) {
				d[i] = d[i - 3] + 1;
			} else {
				if (d[i - 3] != 0 && d[i - 5] != 0) {
					d[i] = Math.min(d[i - 3], d[i - 5]) + 1;
				}
			}
		}
		
		if (d[N] == 0) {
			System.out.println(-1);
		} else {
			System.out.println(d[N]);
		}
	}

}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/0b35175422b907cc84004848fe7abdd6ae814627

참고

https://st-lab.tistory.com/72

https://sohee-dev.tistory.com/24