[BOJ/Silver 5] 백준 32281 유리구슬 (Glass Bead)(C++)

문제 링크

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

 

문제

투명한 유리구슬처럼 보이지만
그렇게 쉽게 깨지진 않을 거야
사랑해 너만을 변하지 않도록
영원히 널 비춰줄게

 

유리구슬로 깨지지 않을 구조물을 만들고자 한다.

구조물은 다음과 같은 피라미드 격자의 (x, y)에 유리구슬을 놓아 만들어진다. (x, y는 0 이상의 정수)

 

 

 y > 0인 좌표의 구조물이 깨지지 않도록 하기 위해서, 구조물은 다음 조건을 충족해야 한다.

•  (x, y)에 유리구슬이 있으려면 (x, y − 1), (x + 1, y − 1)에 모두 유리구슬이 있어야 한다.

구조물의 y = 0 부분의 정보가 주어졌을 때, y > 0인 곳에 유리구슬을 적절히 놓아 만들 수 있는 구조물의 유리구슬 개수의 최댓값을 구하여라.

 

입력

첫째 줄에 정보가 주어질 범위 N이 주어진다.

둘째 줄에 구조물의 y = 0인 곳의 정보가 길이 N의 문자열 형식으로 주어진다.

문자열의 i번째 문자가 1이라면 (i − 1, 0)에 유리구슬이 있고, 아니라면 유리구슬이 없다. (1 ≤ i ≤ N)

범위를 벗어나는 (x, 0) (x ≥ N)에는 유리구슬이 없다.

 

출력

첫째 줄에 구조물의 유리구슬 개수의 최댓값을 출력한다.

 

제한 

•  1 ≤ N ≤ 200,000

 

 

예제 입력 1

8
11011101

예제 출력 1

10

 

노트

 

답이 C++의 int 범위를 넘어갈 수 있으므로 long long 자료형을 사용하는 것을 추천한다.

 

알고리즘 분류

• 수학

 

풀이

유명한 투리구슬

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define MAX 200001
#define LL long long
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;
int N;
LL DP[MAX];
string S;
LL Answer;

void input() {
    cin >> N;
    cin >> S;
}

void settings() {
    for (int i = 1; i <= N; i++) {
        DP[i] = DP[i - 1] + i;
    }
    LL Count = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] == '0') {
            Answer += DP[Count];
            Count = 0;
        }
        else {
            Count++;
        }
    }
    Answer += DP[Count];
}

void print_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    print_Answer();

    return 0;
}