백준 32806 (C++) Average Substring Value

최초 업로드: 2025-10-03 09:53:11

최근 수정 시간: 2025-10-03 09:53:11

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] Average Substring Value

[문제 링크](https://www.acmicpc.net/problem/32806)

## 문제 설명

Let $s$ be a nonempty string consisting entirely of base-$10$ digits (<code>0</code>-<code>9</code>). If the length of $s$ is $n,$ number the digits $1, 2, 3, \ldots, n$ from left to right, and for $1 \leq i \leq j \leq n,$ let $s[i,j]$ denote the substring consisting of the digits from position $i$ to position $j$, inclusive. (It follows that we are only considering nonempty substrings.) Assign a value to each substring that is simply equal to the largest digit in the substring. What is the average value of the substrings of $s$?

Note that two different substrings may be identical (as strings), but for the purposes of this problem they are treated as distinct. For example, if $s = $<code>1010</code>, then $s[1,2] = s[3,4] = $<code>10</code> are distinct substrings (both with value $1$).

## 입력

The input is a single nonempty string, $s,$ of base-$10$ digits. The length of $s$ is at most $200\,000$.

## 출력

Output a line containing the average value of the substrings of $s$. If the average is an integer, print the integer. If the average is a proper fraction, i.e., is equal to $a/b$, where $a$ and $b$ are positive integers and $a < b$, print this fraction in lowest terms, with a '<code>/</code>' symbol separating the numerator and denominator. If the average is greater than $1$ and does not simplify to an integer, print the whole part followed by the proper fractional part, separated by a space, with the proper fractional part in lowest terms and formatted as described in the previous sentence.

## 풀이
각 자리수가 나온 최대 위치를 기록하며 그 숫자로 한번에 구간을 점프하며 점수를 더해주었다.

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

typedef long long ll;

int existIdx[10], dp[200'001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    s = "0"+s;

ll sum=0;
 for(int i=1;i<s.length();i++) {
 int cur = s[i]-'0', idx=i;
 existIdx[cur] = i;
 while(idx) {
 int nextIdx=0;
 for(int j=cur+1;j<=9;j++) nextIdx = max(nextIdx, existIdx[j]);
 dp[i] += cur * (idx-nextIdx);
 cur = s[nextIdx]-'0';
 idx = nextIdx;
 }
 sum += dp[i];
 }

ll total = s.length()*(s.length()-1)/2;
    ll gcdVal = gcd(sum, total);
    total /= gcdVal;
    sum /= gcdVal;

if(sum/total) cout << sum/total << ' ';
 if(sum==0) cout << "0";
 else if(total!=1) cout << sum%total << '/' << total;
}
```