[백준 19947] 투자의 귀재 배주형

www.acmicpc.net/problem/19947

19947번: 투자의 귀재 배주형

 

쉬운 dp문제

직관적으로 접근하면 dp를 3row로 접근하면 된다. 어차피 y가 10이라는 작은 숫자이므로 메모리초과는 없다..

 

처음 코드:

#include <stdio.h>
#include <algorithm>

using namespace std;

int dp[3][11];
int main(void)
{
  int h, y;
  scanf("%d %d", &h, &y);
  dp[0][0] = dp[1][0] = dp[2][0] = h;

  for (int i = 1; i <= y; i++)
  {
    if (i >= 1)
      dp[0][i] = max(dp[0][i - 1],
                     max(dp[1][i - 1], dp[2][i - 1])) *
                 (1 + 0.05);

    if (i >= 3)
      dp[1][i] = max(dp[0][i - 3],
                     max(dp[1][i - 3], dp[2][i - 3])) *
                 (1 + 0.2);

    if (i >= 5)
      dp[2][i] = max(dp[0][i - 5],
                     max(dp[1][i - 5], dp[2][i - 5])) *
                 (1 + 0.35);
  }

  printf("%d\n", max(dp[0][y], max(dp[1][y], dp[2][y])));
  return 0;
}

 

다른 사람의 코드를 보았다.

좀 더 간단하게 코드를 짜보자. (메모리 사용정도는 같다..ㅎ)

 

A방식의 경우 매해 업데이트되기 때문에 조건을 따로 붙이지 않고 제일 먼저 DP[I]에 값을 넣는다.

B방식의 경우 3년에 한번 업데이트 된다. 따라서 A방식을 적용한 것보다 크면 업데이트 아니면 A방식을 적용한대로 냅둔다.

C방식도 마찬가지 그러면 DP가 일차원 배열이어도 문제 풀이가 가능!!!

#include <stdio.h>
#include <algorithm>

using namespace std;

int dp[11];
int main(void)
{
  int h, y;
  scanf("%d %d", &h, &y);
  dp[0] = h;

  for (int i = 1; i <= y; i++)
  {
    dp[i] = dp[i - 1] * (1.05);

    if (i >= 3)
      dp[i] = max(dp[i], (int)(dp[i - 3] * (1.2)));

    if (i >= 5)
      dp[i] = max(dp[i], (int)(dp[i - 5] * (1.35)));
  }

  printf("%d\n", dp[y]);
  return 0;
}