Codeforces #634 Div2 A. Sequence with DigitsOnlineJudge2020. 5. 20. 23:44
Table of Contents
반응형
코드포스 634회 Div2 A번 문제풀이
https://codeforces.com/contest/1355/problem/A
아래의 식을 만족한다.
an+1 = an + minDigit(an) * maxDigit(an)
<입력>
케이스의 수 t와
정수 a, k가 입력된다.
<예시입력>
1) a=1, k=4 일 때 ak = 42
2) a=487, k=1 일 때 ak = 487
3) a=487, k=2 일 때 ak = 519
4) a=487, k=7 일 때 ak = 628
a1이 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)
반응형
'OnlineJudge' 카테고리의 다른 글
Educational Codeforces Round 100 (Rated for Div. 2) B. Find The Array 풀이 (0) | 2020.12.18 |
---|---|
Educational Codeforces Round 100 (Rated for Div. 2) A.Dungeon (0) | 2020.12.18 |
백준 5676 음주코딩/세그먼트트리 (0) | 2020.12.15 |
Educational Codeforces Round 88 (Rated for Div. 2) A - Berland Poker 풀이 (0) | 2020.05.30 |
Educational Codeforces Round 88 (Rated for Div. 2) B - New Theatre Square 풀이 (0) | 2020.05.29 |
@CODe_ :: 강승현입니다
가파른 성장을 이루고자 노력하는 개발자입니다. 정리하고, 설명하고, 이해시키는 과정으로 보람을 느낍니다. 개발과 관련된 다양한 정보를 몰입감있게 전달합니다.