글 읽기 - 5696번 시간초과

dnwls4659 2년 전 0

배열을 활용해서 작성했는데 시간초과가 나와서 애먹는 상황입니다.. 브루트포스 탐색 방식으로 일일이 받아와서 계산해줘서 시간초과가 나온 것 같은데 혹시 다른 좋은 방법이 있나요? 생각해봐도 잘 모르겠어서 질문드립니다.

import sys
input = sys.stdin.readline

arr = [0] * 10
while True:
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        break
    for i in range(A, B+1):
        i = str(i)
        if len(i) == 1:
            arr[int(i)] += 1
        else:
            for j in range(0, len(i)):
                arr[int(i[j])] += 1
                
    for k in arr:
        print(k, end = " ")
    print()
    arr = [0] * 10

slah007 2년 전 1

일단 0은 까다로우므로 생각하지 말고, 어떤 d가 k번째 자리에 오는 _ _ _ d _ _ 상황에서 다른 숫자들을 채워 A 이상 B 이하가 되도록 하는 경우의 수를 생각해 보세요. 모든 가능한 d와 k에 대해 경우의 수를 다 세면 그게 d가 나올 수 있는 전체 개수가 됩니다.

더 생각해 보면 A 이상 B 이하는 까다로우므로 (B 이하인 경우의 수) - (A-1 이하인 경우의 수) 로 세면 됩니다.

예를 들어 A = 12, B = 321이고 d = 1을 셀 때

_ _ d라면 B 이하인 것은 _ _ 1 ~ 3 2 1이므로 33개이고

_ d _라면 B 이하인 것은 _ 1 0 ~ 3 1 9이므로 40개이고

d _ _라면 B 이하인 것은 1 0 0 ~ 1 9 9이므로 100개입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

5696번 시간초과

dnwls4659 2년 전 0

slah007 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말