글 읽기 - 주식 그리디

jk6722 2년 전 0

도저히 안 풀려서 질문 드립니다.. 주식 가격을 모두 알고 있으니까 절대 손해보지 않는 방향으로 가면 되겠다고 생각했습니다.

1. 아무것도 안하고 다음날로 넘어간다.

2. 만약 다음날 주가가 떨어진다면 풀매도 한다.

3. 만약 다음날 주가가 오른다면 풀매도하고 풀매수한다.

이런 규칙을 세워서 해보려 했는데 어디서 틀린건지 잘 모르겠네요.

매수가 가능할 때만 대출을 받는다는 조건은 넣어줬습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int INF = INT_MAX;
const int MAX_N = 10 + 5;
int N, M, K;
int P[MAX_N]; //주식 가격
int ans;

void timetravel(int depth, int Coin, int cnt, int loan) {
	if (depth == N) {
		ans = max(ans, Coin + P[depth] * cnt);
		return;
	}
	ans = max(ans, Coin + P[depth] * cnt);
	timetravel(depth + 1, Coin, cnt, loan);
	if (P[depth] > P[depth + 1]) {
		//내일 가격이 떨어진다면 풀매도 후 기다린다
		int now_money = Coin + P[depth] * cnt;
		timetravel(depth + 1, now_money, 0, loan);
	}
	else if (P[depth] < P[depth + 1]) {
		//내일 가격이 오른다면 오늘 풀매수 해야함
		int now_money = Coin + P[depth] * cnt; //풀매도하고
		if(cnt > 0)
			timetravel(depth + 1, now_money, 0, loan);
		if ((now_money - loan) * (K + 1) >= P[depth]) { //매수가 가능하다면?
			now_money -= loan; //대출 갚고
			int new_loan = now_money * K; //다시 대출
			now_money += new_loan;
			int new_cnt = now_money / P[depth];
			now_money = now_money - ( P[depth] * new_cnt);
			timetravel(depth + 1, now_money, new_cnt, new_loan);
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> K;
	ans = M;
	for (int i = 1; i <= N; i++)
		cin >> P[i];
	timetravel(1, M, 0, 0);
	cout << ans << "\n";
	return 0;
}

qvixnh22 2년 전 1

큰 입력

10 1000 4
100 1000 100 1000 100 1000 100 1000 100 1000

와 같은 입력에도 ans가 int 범위 내에 있을까요?

jk6722 2년 전 0

아하 범위를 생각못했네요. 감사합니다

그런데 long long으로 바꿨는데도 틀렸으면 알고리즘이 틀린거겠죠???

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

주식 그리디

jk6722 2년 전 0

qvixnh22 2년 전 1

jk6722 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말