백준 25822, 2000문제 푼 임스

개요

문제 링크
실버 1, DP
0이 일정 개수 미만으로 포함된 최장 연속구간의 최댓값

---

접근

1. 0은 max(2, c/99)까지 가능하다.

2. 3개 값을 저장한 dp를 사용한다. dp[i][j] = i번째까지 j번 스트릭프리즈를 사용한 최대길이

3. 각 dp에 2개의 값을 저장한다. 하나는 길이, 하나는 최댓값

4. dp를 돌때 값이 0이면 dp[i-1][j-1]과, 0<이면 dp[i-1][j]와 연산해주면 됨.
   팁 : 입력을 받아올 때 double을 쓰기 싫다면 아래와 같이 한다.

   scanf("%1d.%2d");

---

Pseudo code

if (value == 0)
    dp[current][strick] = dp[previous][strick-1]+1;
else
    dp[current][strick] = dp[previous][strick]+1;

---

Source code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x, y, c;
    scanf("%1d.%2d", &x, &y);
    c = (x*100+y)/99;

    int n;
    cin >> n;
    int a[n+1];
    for (int i=1; i<=n; i++)
        cin >> a[i];
    int dp[n+1][3][2];
    for (int j=0; j<3; j++) {
        dp[0][j][0] = 0;
        dp[0][j][1] = 0;
    }
    for (int i=1; i<=n; i++) {
        if (a[i]) {
            for (int j=0; j<3; j++) {
                dp[i][j][0] = dp[i-1][j][0]+1;
                dp[i][j][1] = max(a[i],dp[i-1][j][1]);
            }
        } else {
            dp[i][0][0] = 0;
            dp[i][0][1] = 0;
            for (int j=1; j<3; j++) {
                if (c >= j) {
                    dp[i][j][0] = dp[i-1][j-1][0]+1;
                    dp[i][j][1] = dp[i-1][j-1][1];
                } else {
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                }
            }
        }
    }
    int ans = 0, cnt = 0;
    for (int i=1; i<=n; i++)
        for (int j=0; j<3; j++)
            if (ans <= dp[i][j][0]) {
                ans = dp[i][j][0];
                cnt = max(cnt,dp[i][j][1]);
            }
    cout << ans << '\n' << cnt;
}