백준 2839번

문제 태그에는 다이나믹 프로그래밍을 사용하라고 쓰여져 있다. 나는 조금 다른 방법을 생각해보기로 했다.

출력값이 -1(3, 5로만 표현할 수 없는 숫자를 입력했을 경우)이 되지 않는 수들은 대부분 이렇게 나타낼 수 있다.

X = 3 + ... + 3 + 5 + ... + 5

3의 개수를 x, 5의 개수를 y라고 할 때

둘 다 0일 경우 : X의 값은 0이다.
y만 0일 경우 : X는 3의 배수이다.
x만 0일 경우 : X는 5의 배수이다.
둘다 1 이상일 경우 : 특정한 숫자
위의 규칙을 따르지 않는 숫자들도 존재

가 된다. 하지만 이런 규칙만 보고 코드를 짜면 좋지 않은 결과가 나올 것이다. 우선 위 규칙들의 순서를 잘 생각해보자.

X는 3의 배수일수도, 5의 배수일수도 있다. 이는 15, 30등과 같은 15의 배수를 나타낸다. 이러한 수들이 나왔을 때, 당연히 5의 배수로 나누는 것이 최소값이 나올 것이다. 그러므로, 5로 나누는 과정을 먼저 거쳐야한다.

만약 5로 나뉘어서 나뉘어 떨어지지 않는 수라면, 3으로 나눠진다는 뜻이다. 그러면 3을 한 차례씩 빼면서 5로 나뉘어 떨어질 수 있는 수를 찾는 것이 현명할 것이다. 5가 3보다 크므로, 5kg짜리가 최대한 많아야 최소값이 나올 수 있기 때문이다. (1번)

이렇게 3을 한 차례씩 빼면서 5의 배수를 찾으면, 3을 뺀 횟수와 남은 숫자를 5로 나눈 몫을 더한 값을 출력한다 (2번). 만약, 3을 계속 빼면서 남은 값이 1과 2라면, 더이상 5로 나눌수가 없게 되면서 문제의 조건에도 맞지 않게 된다. 이러한 경우 -1을 출력한다. (3번) 남은 값이 0이라면, 3을 뺀 횟수만을 출력하면 될 것이다. (4번)

#include <stdio.h>

int main(void) {
	int kilo_total;
	scanf("%d", &kilo_total);
	int kilo_3 = 0;
	if (kilo_total % 5 == 0) {
		printf("%d\n", kilo_total / 5); // (1번)
	}
	else {
		for (;;) {
			kilo_total -= 3;
			kilo_3 += 1;
			if (kilo_total % 5 == 0) {
				printf("%d\n", kilo_3 + (int)(kilo_total / 5)); // (2번)
				break;
			}
			if (kilo_total == 1 || kilo_total == 2) {
				printf("-1\n"); // (3번)
				break;
			}
			if (kilo_total == 0) {
				printf("%d\n", kilo_3); // (4번)
				break;
			}
		}
	}
}