[BOJ 24885] 백준 24885번 - 주식
| 2022 숭고한 연합 알고리즘 콘테스트 Open Contest 풀이 | ||
|---|---|---|
| A | [BOJ 24883] 자동완성 | |
| B | [BOJ 24884] 장작 넣기 | |
| C | [BOJ 24885] 주식 | |
| D | [BOJ 24886] SKH 문자열 | |
| E | [BOJ 24887] 최대한의 휴식 | |
| F | [BOJ 24888] 노트 조각 | |
| I | [BOJ 24891] 단어 마방진 |
1. 문제
$24885$. 주식 (2022 숭고한 연합 알고리즘 콘테스트 C번)
2. 풀이
문제의 조건을 번호를 붙여 구분하여 정리해본다.
- 주식을 쪼개서 매수할 수 없다.
- 주식을 매수하지 않는다면 대출받을 수 없다.
- 대출금이 있을 경우 모두 상환하기 전까지 대출받을 수 없다.
- 주식을 매도해서 번 돈은 매도하는 즉시 들어온다.
- 주식을 매수하면 다음 날부터 매도할 수 있다. (매도한 당일 매수는 가능)
- 돌아올 때는 대출금을 갚지 않고 돌아와도 무방하다.
- 돌아올 때 주식은 전부 매도한 상태로 돌아와야 한다.
$N\leq 10$이고, 각 날마다 취할 수 있는 행동은 총 네 가지가 있다. (조건5에 의해서 하루동안 매수 후 매도의 순서는 불가능하다.)
| 매도 | X | X | O | O |
|---|---|---|---|---|
| 매수 | X | O | X | O |
따라서 총 경우의 수는 $4^{10}\fallingdotseq 1,000,000$ 이어서 시간 안에 브루트포스를 돌릴 수 있다.
다루는 값은 총 네 개이다.
- $day$ $\rightarrow$ 현재 날짜
- $money$ $\rightarrow$ 보유금액
- $stock$_$cnt$ $\rightarrow$ 갖고 있는 주식 개수
- $loan$ $\rightarrow$ 대출금액
1. 매도 X, 매수 X
- 그대로 다음 날짜로 넘어간다.
2. 매도 X, 매수 O
조건3에 의해서 $loan\neq 0$인 경우, 갖고 있는 돈 $money$로 $loan$을 갚는다. ($money\lt loan$여서 $loan$을 전부 갚지 못할 수도 있다.)- (대출금을 갚고 나서) $loan= 0$인 경우, $money\times K$만큼의 대출금을 얻는다.
조건2에 의해서 주식을 하나라도 살 수 있는 경우, $p[i]$ 가격의 주식을 $stock$_$cnt$ 만큼 전부 산다.
3. 매도 O, 매수 X
- $stock$_$cnt$만큼의 보유한 주식을 전부 판다.
조건6에 의해서 이 날이 매도한 마지막 날일 수 있으므로, 주식을 판 즉시 $loan$을 갚는 행동을 취하지 않는다.
4. 매도 O, 매수 O
- 위의
매도 O, 매수 X하는 경우와매도 X, 매수 O하는 경우를 합친다.
5. day=N 인 경우
조건7에 의해 주식을 전부 팔고, $money$의 최댓값을 갱신한다.
돈의 최댓값이 어느 값까지 가능한지 알아보기 위해 다음의 극단적이면서 단순한 예시를 들어보자.
$N=10, M=1000, K=4$
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| P[i] | 100 | 1000 | 100 | 1000 | 100 | 1000 | 100 | 1000 | 100 | 1000 |
| 매도 | X | O | X | O | X | O | X | O | X | O |
| 매수 | O | X | O | X | O | X | O | X | O | X |
돈을 $x$원 가지고 있으면, 매도할 때 $4x$의 금액을 빌려 $5x$로 $100$원 주식을 사서 $1000$원에 팔고 대출금 $4x$를 갚는다. 이를 식으로 정리하면 다음 날 갖게 되는 돈은 $(5x\div 100)\times 1000-4x=46x$ 이므로 원래 돈의 46배씩 불어난다.
따라서 $1000\times 46^5\fallingdotseq 200,000,000,000$ 이므로, int 범위를 훨씬 넘어간다. (마지막 날에는 대출금을 갚지 않지만, 이는 위 값에 비해 사소하므로 무시한다.) 그러므로, $money$를 다루는 변수의 자료형들은 long long int를 사용해야 한다.
3. 채점 결과
4. 회고
위에서 설명한, 돈의 최댓값의 크기를 계산하지 않고 int자료형을 사용하여 WA를 한 번 받았다. 극단적인 값을 염두에 두는 습관을 들여야겠다.
댓글남기기