백준 1748 - 수 이어 쓰기1

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

1748번: 수 이어 쓰기 1

 

 

스스로 풀기는 했지만 시간이 오래걸렸기 때문에, 포스팅하며 코드를 리뷰해보고자 한다.

 

위 문제는 임의의 수 N을 입력받아 1부터 N까지를 이어서 쭉 썼을 때, 전체의 자릿수를 구하는 문제이다.

 

아마 반복문으로 N까지 돌리면 시간초과가 나올 것이다.

따라서, 나는 입력받은 수의 자릿수를 구해서 반복문 통해 해결하였다.

 

 

알고리즘을 정리하자면 다음과 같다.

 

전체 자릿수를 구해주기 위해서는

각 자릿수의 갯수 * 각 자릿수의 길이를 해주어야 한다.

예를들면 십의 자릿수를 갖는 수는 10~99까지 총 90개가 존재하므로, 90*2가 된다.

(십의 자릿수를 갖는 수의 갯수 = 십의 자릿수에 올 수 있는 경우의 수 9 * 일의 자릿수에 올 수 있는 경우의 수 10)

 

위와 같은 방식으로 백의 자릿수도 구해보자.

백의 자릿수를 갖는 수의 갯수 = 100~999까지 존재

백의 자릿수에 올 수 있는 경우의 수: 9 (1~9)

십의 자릿수에 올 수 있는 경우의 수: 10 (0~9)

일의 자릿수에 올 수 있는 경우의 수: 10 (0~9)

따라서, 9*10*10 = 900이 된다.

 

여기서 규칙을 찾아보자면,

숫자의 맨 앞에 올 수 있는 경우의 수는 항상 9개이고 (1~9)

맨 앞을 제외한 나머지 자릿수에 올 수 있는 경우의 수는 항상 10개(0~9)라는 것을 알 수 있다.

 

자릿수가 늘어날수록, 9*10*10*10... 계속 10을 곱해주면 된다.

 

입력받은 숫자가 몇 자릿수인지 파악한 후, 해당 자릿수 -1 까지는 위의 방식으로 갯수를 세어 계산하면 된다.

왜 입력받은 숫자의 자릿수 - 1 이냐면

위에서 계산한 갯수들은 해당 자릿수를 갖는 모든 경우의 수이기 때문에 만약 300을 입력받는다고 치면 1~300까지 이어서 쭉 쓰므로, 당연히 두 자릿수의 수들은 모두 갖게 되지만 세 자릿수는 100~999까지 이므로 다 포함하면 안된다.

따라서, 입력받은 숫자의 자릿수 - 1 까지만 모든 경우의 수를 갖게 되는 것이다.

 

위 알고리즘을 토대로 구현하기 위해서는 

 

1. 입력받은 수의 자릿수 파악하기

입력받은 숫자의 자릿수 - 1까지 위의 알고리즘을 적용한다.

단, 일의 자릿수는 9개이므로 입력받은 숫자의 자릿수가 일의 자릿수가 아닐 경우, 9를 더해주었다.

 

2. 입력받은 수가 두 자릿수 이상인 경우

위에서 일의 자릿수는 걸렀으므로, 두 자릿수부터는 반복문을 통해 해결한다.

입력받은 숫자의 자릿수 -1 까지는 모든 경우의 수를 갖게 되므로

입력받은 숫자의 자릿수 - 1까지는 모든 경우의 수와 해당 자릿수의 길이를 곱하여 더해주고

 

입력받은 숫자의 자릿수에서는 따로 계산이 필요하다.

예를 들어 321의 경우에 세 자릿수의 갯수를 세어보자

100~199 => 맨 앞 1 고정 & 2, 3번째 자릿수에 올 수 있는 경우의 수 = 10 * 10 = 100

100~199,200~299 맨 앞의 수(백의 자릿수)가 1, 2일 때까지는 위와 같은 갯수를 갖고

==> 규칙화해보자면, 

(맨 앞의 수 - 1) * (맨 앞을 제외한 각 자릿수에 올 수 있는 모든 경우의 수) * (해당 자릿수의 길이) 이다.

맨 앞을 제외한 각 자릿수에 올 수 있는 모든 경우의 수는 해당 자릿수 - 1만큼 계속 10을 곱해줌으로써 구할 수 있다.

(맨 앞을 제외한 자릿수의 갯수는 n-1개 이고 n-1만큼 10을 곱해주면 되기 때문)

 

300~321까지는 21 + 1의 갯수를 갖는다.

그럼 맨 처음 입력받을 때 맨 앞을 제외한 수 (21)를 남겨두고 + 1을 해주면 된다.

 

위와 같은 알고리즘을 구현한 코드는 다음과 같다.

 

n = input()
l = len(n)
n1 = int(n)
if n1>=10:
    n2 = list(n)
    n3 = n2[0]
    n2 = n2[1:]
    n2 = "".join(n2)
    n2 = int(n2)
    n3 = int(n3)

cnt = 0
tmp = 9
tmp2 =1
if l ==1:
    cnt = n1

else:
    cnt += 9
    for i in range(2, l+1):
        if i != l:
            tmp *= 10
            cnt += i*tmp
        else:
            for j in range(1,i):
                tmp2 *= 10
            cnt += l*(n3-1)*tmp2
            cnt += l*(n2+1)

print(cnt)

여기서 n2가 맨 앞의 수를 제외한 수이고

n3는 맨 앞의 수이다.