문제 링크
문제 요약
주어진 숫자 문자열 S를 두 개의 숫자 i와 n으로 분리하는 방법의 수를 찾아야 합니다.
여기서 i는 현재 페이지 번호, n은 전체 페이지 수를 의미합니다. 분리된 i와 n은 다음 조건을 만족해야 합니다:
i와n은 선행 0을 가질 수 없습니다 (예: “01”은 유효하지 않습니다.)i는n보다 작거나 같아야 합니다 (i <= n).
풀이
이 문제는 주어진 숫자 문자열 S를 가능한 모든 방법으로 두 부분으로 나누어 보고, 각 분할이 문제의 조건을 만족하는지 확인하는 방식으로 해결할 수 있습니다.
- 모든 분할 지점 탐색: 문자열
S의 길이가L이라고 할 때, 분할 지점은 첫 번째 문자 바로 뒤부터 마지막 문자 바로 앞까지 가능합니다. 즉,S[0...k-1]가i가 되고,S[k...L-1]가n이 되는 모든k에 대해 확인합니다. - 선행 0 검사: 분리된
i와n문자열이 각각 길이가 1을 초과하면서 ‘0’으로 시작하는 경우(예: “01”, “007”)는 유효하지 않으므로 건너뜁니다. 길이가 1인 ‘0’ 자체는 이 문제에서는 페이지 번호가 1부터 시작하므로 유효하지 않습니다. (코드는a[0] == '0' or b[0] == '0'로 처리하는데, 이 경우a나b가 ‘0’ 자체일 때도 걸러지므로 문제 조건에 부합합니다. 페이지 번호는 1부터 시작합니다.) i <= n조건 검사:- 자릿수 비교:
i의 자릿수와n의 자릿수를 먼저 비교합니다.- 만약
i의 자릿수가n의 자릿수보다 작다면 (len(i) < len(n)),i는 항상n보다 작으므로 유효한 분할입니다. - 만약
i의 자릿수가n의 자릿수보다 크다면 (len(i) > len(n)),i는 항상n보다 크므로 유효하지 않은 분할입니다.
- 만약
- 같은 자릿수일 경우:
i와n의 자릿수가 같다면 (len(i) == len(n)), 두 문자열을 정수로 변환하여 직접int(i) <= int(n)조건을 확인합니다. 이 경우에만 정수 변환이 필요하며, 자릿수가 다를 때는 문자열 길이 비교만으로 판단할 수 있어 효율적입니다.- Python에서는 이를 쉽게 할 수 있지만 타 언어의 경우, 주어지는 숫자의 길이가 크기 때문에 int array로 입력을 받아 모든 자릿수를 처리하는 작업을 처리해야 할 수 있습니다.
- 자릿수 비교:
이러한 조건들을 모두 만족하는 분할의 수를 세어 최종 답을 출력합니다.
정답 코드
def solve():
s = input()
ans = 0
# 모든 가능한 분할 지점을 순회
# i는 첫 번째 부분(a)의 길이이자, 두 번째 부분(b)의 시작 인덱스
for i in range(1, len(s)):
a = s[:i] # 첫 번째 부분 (i)
b = s[i:] # 두 번째 부분 (n)
# 선행 0 검사
# '0'으로 시작하는 숫자는 유효하지 않음 (단, 숫자 자체가 '0'인 경우는 예외이나, 페이지 번호에서는 해당 없음)
# 여기서는 '0'으로 시작하는 모든 경우를 필터링
if a[0] == '0' or b[0] == '0':
continue
# i <= n 조건 검사
# 1. i의 자릿수가 n의 자릿수보다 큰 경우: i > n 이므로 유효하지 않음
if len(a) > len(b):
continue
# 2. i의 자릿수가 n의 자릿수보다 작은 경우: i < n 이므로 유효함
if len(a) < len(b):
ans += 1
continue
# 3. i와 n의 자릿수가 같은 경우: 실제 값 비교
if int(a) <= int(b):
ans += 1
print(ans)
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()