Codeforces #634 Div2 A. Sequence with Digits

코드포스 634회 Div2 A번 문제풀이

 

https://codeforces.com/contest/1355/problem/A

Problem - A - Codeforces

 

 

아래의 식을 만족한다.

 

a_n+1 = a_n + minDigit(a_n) * maxDigit(a_n)

 

<입력>

케이스의 수 t와

정수 a, k가 입력된다.

 

<예시입력>

1) a=1, k=4 일 때 a_k = 42

2) a=487, k=1 일 때 a_k = 487

3) a=487, k=2 일 때 a_k = 519

4) a=487, k=7 일 때 a_k = 628

 

 

영어를 몰라도 Note를 보면 어떤 문제인지 이해가 될 것이다..

---

 

a₁이 1일 때 k를 계속 증가시켜보면 1, 2, 6, 42, 50, 50, 50... 계속해서 50이 반복된다.

 

k	an+1	ak
1	-	1
2	a2 = a1 + min(a1) * max(a1) = 1 + min(1) * max(1)	2
3	a3 = a2 + min(a2) * max(a2) = 2 + min(2) * max(2)	6
4	a4 = a3 + min(a3) * max(a3) = 6 + min(6) * max(6) = 6 + 6 * 6	42
5	a5 = a4 + min(a4) * max(a4) = 42 + min(4, 2) * max(4, 2) = 42 + 2 * 4	50
6	a6 = a5 + min(a5) * max(a5) = 50 + min(5, 0) * max(5, 0) = 50 + 0 * 5	50

한 번이라도 0이 포함되면 그 이후엔 계속 결과값이 전과 동일하게 유지가 된다.(min 함수에서 계속 0이 선택되니까) 그래서 반복문을 돌릴 때도 0이 있으면 break를 해주면 된다.

 

처음엔 모스 알고리즘이 생각나서 어렵게 풀다가 설마 A번부터 이런 난이도가 나올까 하여 싹 갈아엎고 30분은 잡고 있었다. DP로 풀어도 봤는데 계속되는 시간초과에 다른 문제로 넘어갔고, 643회의 결과는 처참했다.

대회 종료후 Editorial을 보고 나서야 이해를 했다.

 

 

Python3

import sys
input = sys.stdin.readline

def calc(x):
    m1=10
    m2=0
    while x>0:
        y = x%10
        x//=10
        m1=min(m1,y)
        m2=max(m2,y)
    return m1*m2

t = int(input())
while t:
    t-=1
    x,k = map(int,input().strip().split())
    k-=1
    while k:
        k-=1
        y = calc(x)
        if y==0:break	#0이 있으면 break
        x+=y
    print(x)