[11058번] 크리보드

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

이 문제는 선데이코딩에서도 출제된 문제이다.

dp로 접근해야하는데 점화식을 보고 생각해보자.

점화식은 다음과 같다.

DP[i] = j*DP[i-j-1]

DP[i] :: i번째에 A가 가장 많이 나올때의 값이라고 하면

j는 V를 j번 한것이다. 그런데 V를 하기 위해서는 선행적으로 Ctrl - A , Ctrl - C가 필요하다.

따라서 j번째에 V를 한것이라면 j - 1번째에 C를 하게 된 것과 같은 의미가 된다.

소스 코드 : 

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

#include <iostream> #include <cstdio>   #define max(a,b)(a > b ? a : b)   using namespace std;   long long dp[102];   int main() {     int n;     scanf("%d", &n);       for (int i = 1; i <= 6; i++)         dp[i] = i;       for (int i = 7; i <= 100; i++)         for(int j = 1; j <= i - 1; j++)             dp[i] = max(dp[i], j*dp[i - j - 1]);          printf("%lld", dp[n]);          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus