3과 5로 숫자 만들기

http://kldp.org/node/130501

주어진 미숫가루 임의의 n kg에 대하여, 3kg짜리 자루와 5kg짜리 자루로 나눠 담아야 한다. 1kg이상 남으면 안된다.

n mod 5 = 0 이면, 5kg짜리 자루 (n/5)개로 나눠 담을 수 있다.
n mod 5 = 1 이면, 5kg짜리 자루 ((n-5)/5)개로 나눠 담고, 나머지 6kg을 3kg짜리 자루 2개에 나눠 담으면 된다.
n mod 5 = 2 이면, 5kg짜리 자루 ((n-10)/5)개로 나눠 담고, 나머지 12kg을 3kg짜리 자루 4개에 나눠 담으면 된다.
n mod 5 = 3 이면, 5kg짜리 자루 (n/5)개로 나눠 담고, 나머지 3kg을 3kg짜리 자루 1개에 담으면 된다.
n mod 5 = 4 이면, 5kg짜리 자루 ((n-5)/5)개로 나눠 담고, 나머지 9kg을 3kg짜리 자루 3개에 나눠 담으면 된다.

단, n=1, 2, 4, 7인 경우는 어떻게 할 방법이 없다.

이걸 어떻게 하면 조건문 없이 한줄에 쓸 수 있을까 고민해 봤는데, 일단 3kg짜리 자루의 수는 다음과 같다.

((n mod 5)*2 mod 3)

그리고 전체 자루의 수는 다음과 같이 얻을 수 있다. 우선 "/"연산을 정수들끼리 나누어 정수값만 취하고 소숫점 이하는 버린다고 생각하자.
n mod 5 = 0인 경우에는 n/5개
n mod 5 = 1인 경우에는 n/5+1개
n mod 5 = 2인 경우에는 n/5+2개
n mod 5 = 3인 경우에는 n/5+1개
n mod 5 = 4인 경우에는 n/5+2개

위의 내용을 조건문 없이 한줄로 표현할 수 있는데, 잘 살펴보면 n mod 5의 나머지가 mod 3에서 각각 0, 1, 0, 1, 0인 것을 알 수 있다. 여기에 (n mod 5)/3이 각각 0, 0, 0, 1, 1이라는 사실도 알 수 있다.
즉, 0, 1, 2, 1, 2라는 수열은 ((n mod 3) mod 3)+((n mod 5)/3)으로 얻을 수 있다.

따라서, 전체는
(n/5)+((n mod 3) mod 3)+((n mod 5)/3)
개의 자루가 필요하다.

여기서 5kg짜리 자루가 몇개 필요한가 알아내려면, 전체에서 3kg짜리 자루의 수를 빼면 된다.
(n/5)+((n mod 3) mod 3)-((n mod 5)/3)

만약 /연산을 정수들끼리 나누지 않고, 일반적으로 정의하고 싶다면,
n/5를 (n - ((n mod 5) mod 3))/5로 정의하면 된다. 왜 그런가는 각자 생각해 보자.

따라서
전체적으로
((n - ((n mod 5) mod 3))/5) + ((n mod 3) mod 3) + ((n mod 5)/3) 개의 자루가 필요한데,
((n - ((n mod 5) mod 3))/5) + ((n mod 3) mod 3) - ((n mod 5)/3) 개의 5kg짜리 자루와,
((n mod 5)*2 mod 3) 개의 3kg짜리 자루가 필요하다.