[BOJ 3278 // C++] EXCHANGE

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 3278번 문제인 EXCHANGE이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3278 

3278번: EXCHANGE

매 i번째 날에 들고 있을 수 있는 최대 마르크 액수는 그 이전에 가지고 있을 수 있는 최대 달러 액수를 당일 환전하거나 그 이전에 환전해 들고 있는 두 경우의 최댓값으로 구할 수 있고, 최대 달러 액수 또한 이와 유사하게 구할 수 있다.

 

위의 관계를 점화식으로 나타내고, 환전 비율에 신경써 구현해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long double ld;

int N;

ld arr[100][2];
ld dp[100][2]; // [0]: marks, [1]: dollars

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << fixed;
	cout.precision(2);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i][0] >> arr[i][1];

	dp[0][0] = 100, dp[0][1] = arr[0][0];
	for (int i = 1; i < N; i++) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] * (100 / arr[i][1]));
		dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] * (arr[i][0]) / 100);
	}

	cout << dp[N - 1][0];
}