오름차순 자리 & 합
골드 II의견: 0
패턴 분석가 하린은 자리 숫자가 비감소이면서 자릿수 합이 정확히 \(S\)인 양의 정수에 주목한다.
양의 정수 \(x\)의 자릿수 표현 \(d_1 d_2 \cdots d_k\)가 비감소라 함은 \(d_1 \le d_2 \le \cdots \le d_k\)를 만족한다는 뜻이다.
예를 들어 \(1\,159\) (\(1 \le 1 \le 5 \le 9\), 합 \(=16\)), \(3\,334\) (\(3 \le 3 \le 3 \le 4\), 합 \(=13\))은 조건을 만족하지만 \(321\)은 \(3 > 2\)이므로 비감소가 아니다.
구간 \([L, R]\)에서 위 조건을 만족하는 수의 개수를 구하여라.
- \(1 \le L \le R \le 10^{18}\)
- \(1 \le S \le 162\)
한 줄에 세 정수 \(L\), \(R\), \(S\)가 공백으로 구분되어 주어진다.
\(L\) 이상 \(R\) 이하인 정수 중 자릿수가 비감소이고 자릿수 합이 정확히 \(S\)인 수의 개수를 출력한다.
1 100 5
3
자릿수가 비감소이고 합이 \(5\)인 수를 찾는다. 한 자리: \(5\). 두 자리: \(\overline{ab}\), \(a \le b\), \(a+b=5\)이면 \((1,4),(2,3)\) 즉 \(14, 23\). 세 자리 이상은 \(100\) 이하 없음. 총 \(3\)개이다.
10 50 7
3
두 자리 수 \(\overline{ab}\), \(a \le b\), \(a+b=7\): \((1,6),(2,5),(3,4)\) 즉 \(16,25,34\). \(50\) 이하 조건도 만족. 총 \(3\)개이다.
riseoj 작성
출처 Original
평가 및 의견
오름차순 자리 & 합
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
오름차순 자리 & 합