Be myself :: [baekjoon 1500]최대 곱

달력

32024  이전 다음

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

dp로 푼사람이 아무도 없어서 올려본다.

점화식을 세우면 다음과 같다

dp[s][k] = max(dp[s-X][k-1] * X) (1 <= X <= S-1)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int S, K;
	scanf("%d %d", &S, &K);
	vector<vector<long long>> dp(S + 1, vector<long long>(K + 1));
	for (int i = 1; i <= S; i++)
	{
		dp[i][1] = i;
	}

	for (int k = 2; k <= K; k++)
	{
		for (int s = 1; s <= S; s++)
		{
			for (int x = 1; x <= s - 1; x++)
			{
				dp[s][k] = max(dp[s][k], dp[s - x][k - 1] * x);
			}
		}
	}

	printf("%lld\n", dp[S][K]);
}


'Algorithm' 카테고리의 다른 글

[sw expert]모의sw역량테스트 보호필름  (1) 2017.10.09
[baekjoon 11057]오르막 수  (0) 2017.08.12
[baekjoon 11727] 2*n타일링2  (0) 2017.08.11
[algospot]Synchronizing Clocks  (0) 2016.01.28
[Algospot]PICNIC  (0) 2016.01.07
Posted by flack3r
|