[Python/BOJ] 24551. 일이 너무 많아...

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

24551번: 일이 너무 많아...

문제

 

카카오에 7년 경력을 가진 신입 개발자로 입사한 pichulia. pichulia 는 카카오 서비스 중 카카오 지갑 서비스 개발 담당자가 되었다.

카카오 지갑은 사용자가 소유한 디지털 자산과 아이템이 담기는 곳으로써 본인 확인을 거쳐 이용할 수 있는 카카오의 다양한 서비스를 모아볼 수 있는 공간이다.

카카오 지갑에서 제공하는 서비스는 매우 다양하다. 우선 '카카오 인증서'를 통해 각종 금융기관과의 연동 서비스를 지원한다. 그리고 '톡명함'을 통해 나를 돋보이게 만드는 명함을 만들 수 있고, 이 명함을 이용해 개발자 커뮤니티 등, 나를 필요로 하는 사람들과 소통할 수 있다. 게다가 '지갑 QR' 을 이용한 무인 매장 이용 서비스도 지원한다. 이 외에도 많은 서비스를 제공하고 있다.

사용자 입장에서는 진짜 지갑처럼 매우 유용하게 사용할 수 있을 것이다. 하지만 개발자 입장에서는 이 모든 것이 정상적으로 돌아가도록 관리를 해야만 하기 때문에 pichulia 는 언제나 일이 많다.

일이 하나만 있는 것도 힘든데, 이렇게 일이 여러 개가 있다... ㅠㅜ

그래서 pichulia 는 $11$, $111$,$1111$, ⋯$\cdots$ 와 같이 2개 이상의 숫자 $1$로만 이루어진 수를 싫어한다. 게다가 이러한 수를 약수로 가진 수도 싫어한다.

양의 정수 $N$이 주어졌을 때, $1$ 이상 $N$ 이하의 정수 중 pichulia 가 싫어하는 수의 개수를 구해보자. pichulia 는 위에 서술된 특징을 가진 정수를 제외한 모든 수를 싫어하지 않는다고 가정한다.

입력

첫 번째 줄에 문제에서 정의된 정수 $N$이 주어진다. ($1 \le N \le 10^{18}$)

출력

 $1$ 이상 $N$ 이하의 정수 중 2개 이상의 숫자 $1$로만 이루어진 수를 약수로 가지는 수의 개수를 출력한다.

풀이

Code

import sys
from itertools import combinations
input = sys.stdin.readline

# 1. 계산 함수 정의
def calculate(c) :
    # 1-1. 변수 생성
    value = 0
    # 1-2.
    for comb in combinations(array, c) :
        # 1-2-1. 공집합에 해당하는 수 생성
        num = 1
        for x in comb : num *= x
        # 1-2-2. n보다 클 경우 continue
        if num > n : continue
        # 1-2-3. 공집합의 수 더하기
        value += n // num
    # 1-3. 값 리턴
    return value

n = int(input())
# 2. 고려 범위 구하기
array = [int('1' * i) for i in [2, 3, 5, 7, 11, 13, 17] if int('1' * i) <= n]
# 3. flag 선언
flag = 1
# 4. 출력 변수 생성
ans = 0
# 5.
for c in range(1, len(array) + 1) :
    # 5-1. 출력 변수 업데이트
    ans += flag * calculate(c)
    # 5-2. flag 업데이트
    flag *= -1
# 6. 결과 출력
print(ans)