[백준] 29158 큰 수 만들기 게임 (파이썬/Python)

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

29158번: 큰 수 만들기 게임

24/02/15 현재 난이도 플레4

쓰이는 알고리즘: 수학,그리디,정렬

남의 도움을 받았는가?: X

내가 생각하는 난이도: 플레4

 

 

 

 

서론

 

이 문제는 작년 SUAPC 문제이다. 나는 이번 SUAPC에 참여 하는데 팀원들과 작년 SUAPC 문제 세트를 풀던중 이문제를 만나게 되었다.

 

이 문제는 사실 내가 예전에 풀었던 1422번 숫자의 신 그리고 16496번 큰 수 만들기 에서 썼던 기술을 쓴다면 어렵지 않게 풀리는 문제이다.

 

하지만 그 생각을 해내는게 쉬운 일은 아니기 때문에 플레4라는 난이도는 적당한것 같다.

 

 

본론

 

이제 본론으로 들어와서 문제에 대한 이야기를 해보자

 

처음에는 나는 성현이의 숫자만 주어지고 지훈이의 숫자는 주어지지 않으므로 어떻게 해결할까 고민했다.

 

우선 성현이의 숫자는 주어지니까 성현이 부터 생각했다..

 

우선 1번 규칙은 할 수 있으면 하는게  이득이라는 결론이 나왔다.

왜냐하면 예를들어 4라면 2*2로 나눌 수 있으므로 자릿수가 2개가된다 따라서 무조건 커진다

다른 예를 들어보면 한 91 정도를 봐보자 그럼 91= 7*13 이므로 자릿수가 늘어난다 따라서 분해 할 수 있다면 분해하는게 무조건 이득이다

그럼 자릿수가 바뀌지 않는 경우도 있지 않겟는가 25를 보자 25=5*5이다 이러한 경우 또한 25<55이므로 분해하는게 이득이라는 결론에 다다른다.

따라서, 2번 규칙은 실행하지 않는게 이득이라는 결론이 나왔다.

그렇다면 이제 성현이는 최대한 소인수 분해를 해줘야한다. 이제 이렇게까지 두고 생각했다.

'아 그러면 지훈이는 어떻게 해야할까?' 고민하던중 생각을 해봤다 '음 지훈이가 어떤 숫자를 골라도 나는 어차피 소인수 분해를 할거인데 지훈이는 N보다 작은 어떤 수든 가질 수 있다 따라서 생각해봤다 지훈이가 5를 선택하는게 이득일까 4를 선택하는게 이득일까?'

당연히 4다 왜냐하면 4=2*2로 변환되기 때문이다. 또한 6과 7이있으면 당연히 6을 선택해야한다 왜냐하면 6은 2*3 이기 때문이다. 이런 생각과정을 거치던중 문득 이런생각이 들었다 '아 최대한 2의n승으로 만드는게 가장유리한게 아닐까?'

 

예를들어 N이 9라면 지훈이는 8을 갖는게 가장이득일것이다 왜냐하면 2*2*2 3자리가 만들어지기 때문이다. 이런생각을 하던중 그럼 N=7이면? 이때는 2*2보다 2*3을 갖는게 이득 아닌가? 라는 생각이 들었다 그러면 3을 두개이상 갖는 것도 될까? 그럼 무언가*9가 되어야하는데 그걸 선택 할 바에는 무언가*8을 선택해서 무언가*2*2*2로만들어주는게 더 자릿 수가 컷다. 그러면서 떠오른것이 아 3이 선택될 수 있었던 이유는 3이 2보다는 크면서 2**2보다는 작기 때문에 선택 될 수 있었던 거구나 라는것을 깨달았다 그러면 지훈이는 무조건 2^n 꼴의 숫자를 가지거나 3*2^n 꼴의 숫자를 가져야겠구나라는 생각을 가지게 되었다.

 

다음으로 이제 소인수 분해를 한후 그 소인수들을 어떻게 정렬할까? 가 문제가 된다.

이 해결방안이 바로 내가 위에서 말한 숫자의 신 이라는 문제와 큰 수 만들기라는 문제의

메인 아이디어이다.

우선 지훈이의 정렬은 별로 걱정할게 없다.

소인수분해를 했다면 3이 있으면  가장 앞에 두고 나머지 2를 놓으면 되기때문이다.

 

하지만 문제는 성현이의 정렬이다.

우선 나의 답 코드를 보고 성현이의 소인수들을 정렬 한 알고리즘을 소개하겠다.

 

N=int(input())
li=[]
#li는 2^n과 2^(n-1)*3의 값을 담을 리스트
for x in range(100):
    li.append(2**x)
for x in range(100):
    li.append(li[x]*3)
li.sort()
jihun=1
# 아래는 지훈이가 선택할 값을 결정하는 과정
for x in li:
    if x>=N:
        break
    else:
        jihun=x
# realjihun은 지훈이가 소인수분해 한 소인수를 넣을 리스트
realjihun=[]
# 소인수 분해 과정
while jihun!=1:
    if jihun%2==0:
        jihun//=2
        realjihun.append(2)
    elif jihun%3==0:
        jihun//=3
        realjihun.append(3)
# 지훈이의 소인수를 정렬하는 과정
realjihun.sort(reverse=True)
jihundap=''
# 지훈이의 답을 구하는 과정
for x in realjihun:
    jihundap+=str(x)
# 지훈답이 비어있다는건 소인수가 없는거니까 그냥 1임
if jihundap:
    jihundap=int(jihundap)
else:
    jihundap=1
# sung은 성현이의 소인수를 담을 리스트
sung=[]
r=N
sungdap=''
# N을 소인수 분해 해주는 과정 N 의 범위가 10**12 까지이므로 반드시 루트를 해줘야함 여기서부터 정렬하는 법이 들어감 아래서설명함
while N!=1:
    pandan=1

    for x in range(2,int(r**(0.5))+2):
        if N%x==0:
            pandan=0
            sung.append([str(x)*100,len(str(x))])
            N//=x
            break
    if pandan:
        sung.append([str(N)*100,len(str(N))])
        break

sung.sort(reverse=True)
for x in sung:
    d=x[0][:x[1]]
    sungdap+=d
sungdap=int(sungdap)
print(sungdap+jihundap)

 

 

주석을 잘 읽어주길 바란다.(시간초과를 피하기 위해)

 

자 이제 성현이의 소인수를 정렬하는 방법에 대해 이야기해보자

우선 그냥 문자열로 내림 차순 정렬해야하는건 당연하다 11,9 가있으면 당연히 911 이 되어야하기 때문이다.

(숫자로 정렬하면 119가 됨)

그러나 그냥 문자로 내림 차순 정렬하기만 하면 될까? 

바로 문제가 생겨버린다. 바로 [3,31]따위가 들어갔을 때이다.

3과 31을 정렬하면 31,3 으로 정렬되 313이나오게 된다 331이 나와야하는데 여기서 문제가 생기는것 이다.

 

그래서 이문제를 해결하기위해 애초에 소인수를 저장할 때 '3'에 20을 곱해준다(최대 13자리까지 들어올 수 있으므로)

그리고 원래 자릿수를 저장해준다 그 과정이 sung.append([str(x)*100,len(str(x))]) 인 것이다.

그렇게하면  3333333....,3131313313..... 이 나오는데 이미 두번째 자리끼리 비교할때 333333이 크게되므로

정렬또한 [3333.... , 313131....] 으로 올바르게 된다

그래서 하나씩 돌면서 원래 기록했던  원래 숫자의 길이(len str(x)) 만큼 숫자를 잘라서 기록해주면

3333...에서는 길이 1이 저장되어있고 313131... 에서는 길이 2가 저장되어 있으므로

331이 저장되게 된다.

따라서 위 와 같은 코드가 되는것이다.

 

 

 

마지막으로...(문풀과 관련 없으니 안보셔도 됨)

 

 

처음에 이 문제를 풀 때는 저 정렬 알고리즘을 생각하지못하다가 93 을 쳐보고 반례를 찾아 예전 기억이 떠올라

문제를 해결할 수 있었다.

value erorr 이 난 이유는 N이 최소 2인데 N이 2라면 지훈이는 무조건 1을  가져야하는데 내가 자꾸 2나 3으로 소인수 분해하려고했기 때문에 틀렸다. 그래서 추가한 코드가

 

if jihundap:
    jihundap=int(jihundap)
else:
    jihundap=1

 

이다.

 

이 문제를 풀었다면 숫자의 신과 큰 수 만들기도 풀어보기를 추천한다 비슷한 문제이다.