[백준] 11058 - 크리보드

문제

• 링크: https://www.acmicpc.net/problem/11058
• 난이도: Gold IV
• 태그: 다이나믹 프로그래밍

풀이

#include <bits/stdc++.h>

using namespace std;

long long d[1001];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        d[i] = d[i - 1] + 1;
        for (int j = 1; j <= i - 3; j++) 
        {
            long long cur = d[i - j - 2] * (j + 1);
            d[i] = std::max(cur, d[i]);
        }
    }

    cout << d[n] << '\n';
    return 0;
}

리트코드 651번 문제와 동일한 방법으로 해결할 수 있다.

배운 점과 후기

백준 게시물 테스트 겸 올려본다!