[BOJ 23892] 백준 23892번 - 바코드 찢기

		GBS Coding Contest 2021 풀이
A		[BOJ 23885] 비숍 투어
B		[BOJ 23886] 알프수
C		[BOJ 23887] 프린트 전달
D		[BOJ 23888] 등차수열과 쿼리
E		[BOJ 23889] 돌 굴러가유
F		[BOJ 23890] 달팽이팽이
G		[BOJ 23891] 타이어 끌기
H		[BOJ 23892] 바코드 찢기

1. 문제

$23892$. 바코드 찢기 (GBS Coding Contest 2021 Open H번)

백준 23892번 - 바코드 찢기 (https://www.acmicpc.net/problem/23892)

2. 풀이

바코드에서 최대 가치를 만들기 위해 어떻게 쪼개야 할지를 고민해보아야 한다.

쪼갠 문자열의 일부분이 올바른 바코드이고 더 이상 쪼개서 가치를 늘릴 수 없는 경우는 해당 문자열에 ‘()’이 딱 하나 포함되어 있는 경우이다. 이는 ‘()’가 1의 가치를 갖고 나머지는 무시해도 됨을 의미한다. 따라서 바코드에서 ‘()’의 개수를 세서 반복 횟수를 곱하면 된다.

단, 바코드가 ‘)’로 시작하고 ‘(‘로 끝나고 반복 횟수가 2 이상일 경우에는, 이어지면서 추가로 ‘()’가 더 생기게 된다. 이때, 추가로 생기는 ‘()’의 개수는 (반복횟수-1개)만큼이다.

위 두 가지를 조합하여 바코드의 최대 가치를 구할 수 있다.

---

• 음료수 개수: $N$
• 음료수 1개의 가격: $K$
• 처음 가진 돈: $money$
• 음료수를 사서 얻는 돈: $earn$

1. 처음부터 음료수를 구입할 돈이 부족한 경우 $money \lt K \rightarrow$ $0$개 구입
2. 음료수 가격보다 음료수를 사서 얻는 돈이 더 많은 경우 $K \leq money \rightarrow$ 무한 개를 구입 가능하지만, 음료수 개수가 $N$개이므로 $N$개 구입
3. 그 외 $\rightarrow$ 돈이 $money$에서 $K$미만으로 가기 전까지 음료수를 구매하여, ‘$K$원을 잃고 $earn$원을 얻는’ 작업을 반복해서 할 수 있다. 따라서 $(money - K) / (K - earn)$ 만큼 음료수를 구매할 수 있다. (역시나 음료수 개수가 $N$개이므로 $N$과 $minimum$을 확인한다.)

$3$에서 그냥 $money / (K - earn)$로 계산해버리면, 돈이 $K$원보다 적은데 $(K – earn)$이 $K$보다 작다는 이유로 $+1$이 되어버릴 수 있다. 먼저 $K$원을 잃고 그 다음 $earn$원을 얻는 것이기 때문에, $K$원을 잃는 것이 불가능한 작업을 추가해버리면 안 된다.

3. 채점 결과

4. 회고

.

5. 코드