[Gold IV] 게임 - 28423

문제 링크

성능 요약

메모리: 110888 KB, 시간: 196 ms

분류

그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 깊이 우선 탐색

제출 일자

2025년 12월 27일 23:03:50

문제 설명

수학을 잘하는 랑이는 오늘 집사에게 수를 이용한 게임을 배웠다. 이 게임은 양의 정수 $N$을 초깃값으로 가진 상태로 시작한다. $N$의 각 자릿수를 모두 더한 값을 $A$, $N$의 각 자릿수를 모두 곱한 값을 $B$라고 할 때, $A$와 $B$를 순서대로 이어 붙인 수를 $f(N)$으로 표현한다. 예를 들어 $N = 12352$라면 각 자릿수의 합은 $1 + 2 + 3 + 5 + 2 = 13$, 각 자릿수의 곱은 $1 \times 2 \times 3 \times 5 \times 2 = 60$이니 $f(N)$은 이 둘을 순서대로 이어 붙인 $1360$이 된다. $1360$에 다시 위 연산을 적용한다면 $1 + 3 + 6 + 0 = 10$, $1 \times 3 \times 6 \times 0 = 0$이므로 $f(1360) = 100$이 된다. 이 $100$에 다시 연산을 적용하면 $f(100) = 10$이고, 이 결과에 다시 적용한다면 $f(10) = 10$이 된다. 이 게임에서는 $N$이 주어질 때 $f(N)$, $f(f(N))$, $f(f(f(N)))$, $\cdots$ 형태로 계속 나아갈 때 언젠가 $f(x) = x$ 형태가 되는 $x$가 나올 수 있는지 알아내는 것이 중요하다.

$N$에 연산을 계속 적용해서 $x = f(x)$가 되는 $x$가 나오게 된다면 $g(N) = 1$, 나오지 않는다면 $g(N) = 0$으로 표현하자. 단, $N, f(N), f(f(N)), \cdots$ 중 $100\,000$보다 큰 수가 하나라도 존재한다면 계산하기 어려우므로 $g(N) = -1$이라고 표현한다. 예를 들어, $N = 1$이라면 $f(1) = 11$, $f(11) = 21$, $f(21) = 32$, $f(32) = 56$, $f(56) = 1130$, $f(1130) = 50$, $f(50) = 50$ 으로 $50$에서 $f(x) = x$ 형태가 나오기 때문에 $g(1) = 1$이 된다.

양의 정수 $L, R (L \le R)$이 주어질 때, $g(L) + g(L + 1) + g(L + 2) + \cdots + g(R - 1) + g(R)$의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 양의 정수 $L$, $R$이 공백으로 구분되어 주어진다. $(1 \le L \le R \le 100\,000)$

출력

$g(L) + g(L + 1) + g(L + 2) + \cdots + g(R - 1) + g(R)$을 출력한다.

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/28423
 
import sys
input = sys.stdin.readline
 
 
 
def Nc(N):
    def Na(N):
        N_str = (str(N))
        ans = 0
        
        for tempN in N_str:
            ans += int(tempN)
        
        return ans
    def Nb(N):
        N_str = (str(N))
        ans = 1
        
        for tempN in N_str:
            ans *= int(tempN)
        
        return ans
    
    return int(str(Na(N)) + str(Nb(N)))
 
 
l, r = map(int, input().split())
ans = 0
 
for i in range(l, r + 1):
    now = i
    for i2 in range(0, 100):
        tempnow = Nc(now)
        if now == tempnow:
            ans += 1
            break
        elif tempnow > 100000:
            ans -= 1
            break
        else:
            now = tempnow
    ans += 0
    
print(ans)