[Baekjoon] 2839번 설탕 배달 B1 <Short>

2839번 - 설탕 배달

1. 문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

• Input

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

• Output

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

2. 사용 알고리즘

• 수학 (Math)

3. 풀이

해당 풀이는 가능한 한 코드의 길이를 줄이고자 하는 숏코딩 방식으로 구현되었다.

Key point

1. $5n$ kg 의 설탕을 배달할 때, $3$ kg 봉지 $0$ 개, $5$ kg 봉지 $n$ 개가 필요하다. $(n \in \mathbb{N})$
2. $n$ kg 설탕을 배달할 때, $3$ kg 봉지 $a$ 개, $5$ kg 봉지 $b$ 개가 필요하다고 할 때, $n-2$ kg 설탕을 배달할 때는 $3$ kg 봉지 $a+1$ 개, $5$ kg 봉지 $b-1$ 개가 필요하다. $(n \in \mathbb{N}, n > 9)$

3.1. 설탕의 무게가 $10$ kg 미만

봉지	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$3$ kg	$1$	X	$0$	$2$	X	$1$	$3$
$5$ kg	$0$	X	$1$	$0$	X	$1$	$0$
합	$1$	X	$1$	$2$	X	$2$	$3$

3.2. 설탕의 무게가 $5$의 배수

$1$ 보다 큰 정수 $n$ 에 대해 다음과 같은 표를 나타낼 수 있다.

봉지	$5n$	$5n+1$	$5n+2$	$5n+3$	$5n+4$
$3$ kg	$0$
$5$ kg	$n$
합	$n$

$5n+5$	$5n+6$	$5n+7$	$5n+8$	$5n+9$	$5n+10$
$0$					$0$
$n+1$					$n+2$
$n+1$					$n+2$

3.3. $2$ kg 더 가벼운 설탕

설탕의 무게가 $2$ kg 가벼워지면 $5$ kg 봉지가 하나 줄어들고, $3$ kg 봉지가 하나 늘어난다.

봉지	$5n$	$5n+1$	$5n+2$	$5n+3$	$5n+4$
$3$ kg	$0$	$2$	$4$	$1$	$3$
$5$ kg	$n$	$n-1$	$n-2$	$n$	$n-1$
합	$n$	$n+1$	$n+2$	$n+1$	$n+2$

$5n+5$	$5n+6$	$5n+7$	$5n+8$	$5n+9$	$5n+10$
$0$	$2$	$4$	$1$	$3$	$0$
$n+1$	$n$	$n-1$	$n+1$	$n$	$n+2$
$n+1$	$n+2$	$n+3$	$n+2$	$n+3$	$n+2$

3.4. 규칙 찾기

위 표를 통해 1 보다 큰 정수 $n$ 에 대하여

5n+1 - n+1
5n+2 - n+2
5n+3 - n+1
5n+4 - n+2
5n+5 - n+1

와 같은 관계를 갖는다는 사실을 알 수 있다.

3.5. 문제의 확장

이는 곧,

x - y

$$y=f(x)$$

를 만족하는 함수 $f(x)$ 를 구하는 문제로 확장된다.

3.6. $x$ 에 대한 $n$ 의 식 구하기

설탕 ($x$)	$n$에 대한 $x$ 의 식	$n$
$3$	$5n + 3$	$0$
$4$	$5n + 4$	$0$
$5$	$5n + 5$	$0$
$6$	$5n + 1$	$1$
$7$	$5n + 2$	$1$
$8$	$5n + 3$	$1$
$9$	$5n + 4$	$1$
$10$	$5n + 5$	$1$
$11$	$5n + 1$	$2$
$\vdots$	$\vdots$	$\vdots$

위 표의 핵심은 $x$ 의 값을 $5n$ 과 $x$ 를 $5$ 로 나눈 나머지의 합으로 나타낸다는 점이다.

가령, $15$ 는 $5$ 의 배수이므로 $5n \ (n = 3)$, $21$ 은 $5$ 의 배수가 아니므로 $5n$ 과 $21$ 을 $5$ 로 나눈 나머지 $1$ 의 합, $5n + 1 \ (n = 4)$ 으로 나타낼 수 있다.

다만, 계산 상의 편의를 위해 $5$ 의 배수를 $5n$ 이 아닌 $5n + 5$ 로 나타낸다는 차이만 존재한다.

위 표로 비추어볼 때 $n$ 의 값은, $5$ 로 나눈 나머지가 $1$ 인 $x$ 에 대하여 $1$ 씩 증가함을 확인할 수 있고, $x$ 에 대한 $n$ 의 값을 구하면 다음과 같다.

$$ n = \Bigl\lfloor{x-1 \over 5}\Bigr\rfloor $$

3.7. 함수 $f(x)$ 찾기

함수 $f(x)$ 는 다음의 특징을 갖는다.

1. $x$ 의 값이 $4$ 또는 $7$ 일 경우, 정확하게 만들 수 없으므로 $-1$ 을 반환한다.
2. $x$ 의 값이 $7$ 이 아니고 $x - 1$ 을 $5$ 로 나눈 나머지가 짝수인 경우, $n + 1$ 을 반환한다.
3. $x$ 의 값이 $4$ 이 아니고 $x - 1$ 을 $5$ 로 나눈 나머지가 홀수인 경우, $n + 2$ 을 반환한다.

이를 좀 더 자세히 살펴보자.

3.7.1. 함수 $f(x)$ 의 특징 1

$3$ kg 와 $5$ kg 의 봉지로, $4$ kg, $7$ kg 의 설탕을 정확히 만들 수 없다. 따라서 $-1$ 을 반환해야 함이 명확하다. 해당 두 경우를 제외하면 임의의 봉지 무게 $x$ 에 대해 모든 설탕 무게를 만들 수 있다.

3.7.2. 함수 $f(x)$ 의 특징 2

우리는 위에서 설탕의 무게 ($x$) 와 최소 사용 봉지 수 ($y$) 의 관계가 다음과 같음을 확인하였다.

x - y
5n+1 - n+1
5n+2 - n+2
5n+3 - n+1
5n+4 - n+2
5n+5 - n+1

또한 $x$ 에 대한 $n$ 의 식에 대해서도 확인하였다.

$$
n = \Bigl\lfloor{x-1 \over 5}\Bigr\rfloor
$$

식에서 $x$ 가 아닌 $x - 1$ 을 $5$ 로 나누므로, $x - 1$ 을 $5$ 로 나눈 나머지에 대해 살펴볼 필요가 있다. 일단 다음이 만족함을 확인해야 한다.

$x \ \% \ 5$ 가 짝수이면, $(x - 1) \ \% \ 5$ 는 홀수이고,
$x \ \% \ 5$ 가 홀수이면, $(x - 1) \ \% \ 5$ 는 짝수이다.

$x$ 를 $5$로 나눈 나머지가 짝수, 즉 $x - 1$ 를 $5$로 나눈 나머지가 홀수인 $5n + 1$, $5n + 3$, $5n + 5$ 의 세 가지 경우를 살펴보자.

해당 경우는 모두 $n + 1$ 값을 반환하므로, 함수 $f(x)$ 는 다음과 같이 나타낼 수 있다.

$$
f(x) = n + 1 = \Bigl\lfloor{x-1 \over 5}\Bigr\rfloor + 1
$$

한편 해당 조건은 $x = 7$ 일 때도 $x$ 의 조건을 만족하므로, $x \ne 7$ 의 조건이 추가되어야 한다.

3.7.3. 함수 $f(x)$ 의 특징 3

이는 특징 2 와 반대로 $x - 1$ 를 $5$로 나눈 나머지가 짝수인 $5n + 2$, $5n + 4$의 두 가지 경우에 대한 내용이다.

모두 $n + 2$ 의 값을 반환하므로 다음과 같이 나타낼 수 있다.

$$
f(x) = n + 2 = \Bigl\lfloor{x-1 \over 5}\Bigr\rfloor + 2
$$

한편 이 경우 역시 $x = 4$ 일 때도 $x$ 의 조건을 만족하므로, $x \ne 4$ 의 조건이 추가되어야 한다.

---

위 특징을 바탕으로 구한 함수 $f(x)$ 는 다음과 같다.

$$ f(x)= \begin{cases} -1, & x \in \{4, 7\} \\ \lfloor{x-1 \over 5}\rfloor + 1, & x \ne 7 \ \And \ \ (x-1) \ \% \ 5 \in 2 \mathbb{N} \\ \lfloor{x-1 \over 5}\rfloor + 2, & x \ne 4 \ \And \ \ (x-1) \ \% \ 5 \in 2 \mathbb{N} + 1 \end{cases} $$

3.8. 함수 $g(x)$

여기서 새로운 함수 $g(x)$ 를 정의한다.

$$ g(x) = (x-1) \ \% \ 5 \ \% \ 2 + 1$$

함수 $g(x)$ 는 $(x - 1) \ \% \ 5$ 의 값이 짝수이면 $1$ 을, 홀수이면 $2$ 를 반환하도록 설계된 함수이다.

이를 활용하여 함수 $f(x)$ 를 다음과 같이 표현할 수 있다.

$$ f(x)= \begin{cases} -1, & x \in \{4, 7\} \\ \lfloor{x-1 \over 5}\rfloor + g(x), & x \notin \{4, 7\} \end{cases} $$

3.9. 숏코딩

더 효과적인 숏코딩을 위해 발악해보자.

3.9.1. $x - 1$ 를 $x$ 로 만들기

$x$ 대신 $x + 1$ 를 사용하여 나타내보자.

$$ f(x+1)= \begin{cases} -1, & x \in \{3, 6\} \\ \lfloor{x \over 5}\rfloor + g(x + 1), & x \notin \{3, 6\} \end{cases} $$

즉,

$$ f(x+1)= \begin{cases} -1, & x \in \{3, 6\} \\ \lfloor{x \over 5}\rfloor + x \ \% \ 5 \ \% \ 2 + 1, & x \notin \{3, 6\} \end{cases} $$

이것으로 코드를 작성하면 아래와 같아진다.

-1 if x in(3,6)else x//5+x%5%2+1

아직 부족하다. 삼항연산자가 아닌 논리연산자를 사용하여 더욱 줄여보자.

3.9.2. 논리연산자 사용

x in (3, 6) 의 값은 bool 으로 True 또는 False 이지만, -(x in (3, 6)) 의 형태로 나타내면, -1 또는 0 의 값으로 변화한다.

x in (3, 6)	True	False
-(x in (3, 6))	-1	0

x in (3, 6) 이 참이면 -1 을, 거짓이면 x // 5 + x % 5 % 2 + 1 을 출력해야 한다.

이때, Python 논리연산자 (or) 의 특징을 활용해보자.

Python 논리연산자 (or) 특징

• a 가 참이면, a or b == a
• a 가 거짓이면, a or b == b

* Python 논리연산에 대한 자세한 설명은 이 포스팅에서 확인할 수 있다.

x in (3, 6)	True	False
-(x in (3, 6))	-1	0
-(x in (3, 6)) or A	-1	A

A 에 x // 5 + x % 5 % 2 + 1 값을 대입한다면, 명확하게 우리가 원하는 결과가 도출된다.

따라서 최종 코드는 다음과 같다.

-(x in(3,6))or x//5+x%5%2+1

4. 제출 코드

맞았습니다!!

x=int(input())-1;print(-(x in(3,6))or x//5+x%5%2+1)

---

관련 포스팅

• [Python] 논리 연산에 대한 고찰