백준) 1로만들기 파이썬

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

1463번: 1로 만들기

최소한의 횟수로 1을 만들어야 한다

그러려면 최대한 많이빼는게 중요할것같다

3으로 계속나누다가 그냥 1로만드는게 가장 빠르지않을까?

당연하게도 3으로 나누는게 가장 많이 줄이는거니까

 

근데 생각한것만큼 그렇게 간단한것같지 않다 왜냐하면 3으로 나눠질때 3으로 나눌수있다고 했기때문

3으로 나누는방향으로 갈때 어떻게 /2와 -1카드를 배합해야 최소한의 카드만 쓸수있을까

고민이 되었기때문이다

 

아무리 수가 작아도 3을 3으로 나누면 2가 없어지고 2를 2로 나누면 1이 없어지니 일단

나눗셈이 -1보다 나쁠일은 없다

 

그럼간단하게 3으로 나눌수있으면 3으로 나누고 안나뉘면 2로 나누고 안나뉘면 -1을 하는 알고리즘을 만들면 먹힐까?

예를들어 1024가 있다고 하자 소인수로 2만가지니 3으로는 나뉠일이 없다 -1을 하지않는이상

위의 알고리즘에 넣으면 10회가 나올것이다 

 

34를 예를들어보자

위의 알고리즘대로 하지않고 -1을 뺀뒤 3으로 나누면 11이된다

 

알고리즘대로 2번 2로 나누면 8이된다

 

흐음 일단 저 알고리즘대로 구현을 해보자

 

아 바보짓을 했네

예제만봐도 저렇게 야매로 하면 안된다는걸 알려주고있다

10의 경우

10 => 9 => 3 => 1순서로 3번만에 만들수 있으니 말이다

 

줄세우는 방법도 생각났지만 너무 비효율적일것같다 정수가 최대 1000만까지니까

1,2,3,4,5,6~n까지 모든 수의 최소횟수를 대입하는것

 

근데 어떻게 구현할지도 감안잡히고 분명히 시간초과날것같다

 

그다음으로 떠오른 방법은  횟수로 묶어서 모든 경우의 수를 저장하는것이다

이런식이다 한층이 한회

그리다보니 피보나치가 떠올랐다

메모를 사용한 탑다운방식 그러고보니 문제 설명에도 메모기법으로 푸는 문제라고 했었지

 

그리고 재귀된함수들중의 최소값을 찾으면 될것이다 그럼 메모는 예를들어 (3,1)이런식으로 될텐데

그게 최소값이라는걸 어떻게 확신할수도있지? 그러니까

메모이제이션이라는게 메모된걸 활용하는건데 최소값이 메모되지않으면 이상해질텐데

 

그러다가 어차피 메모하는걸 가져다 쓰는건 계산을 빨리하기위해서니 단순계산을 메모하면될까?

라는생각이들었고

memo={}
ans=999999999999999999999
def df(num,count):
    
    if num==1:
        global ans
        if count<ans:
            # print(count)
            ans=count
    else:
        if num%3==0:
            try:
                a=memo[(num, 3)]
                df(a,count+1)
            except:
                memo[(num, 3)]=num//3
                a=memo[(num, 3)]
                df(a,count+1)
        if num%2==0:
            try:
                a=memo[(num, 2)]
                df(a,count+1)
            except:
                memo[(num, 2)]=num//2
                a=memo[(num, 2)]
                df(a,count+1)
        try:
            a=memo[(num, 1)]
            df(a,count+1)
        except:
            memo[(num, 1)]=num-1
            a=memo[(num, 1)]
            df(a,count+1)

df(int(input()),0)
# print(ans)
# print(min(ans))
# print(memo)
print(ans)

모든경우의 수를 조사한뒤 최소횟수를 출력한다

하지만 작은수에도 시간이 굉장히 많이걸렸고 

제출하니 시간초과를 당한다

 

이래저래 모든 방법이 안통하게된나 수학적으로(야매로) 풀수있는지 생각해본다

a=int(input())
ans=0
# 나눗셈 우선순위대로 배열
while a>1:
    if a%3==0:
        a=a//3
        ans+=1
        continue
    elif a>=3 and a%3==1:
        a=a-1
        ans+=1
        continue
    # elif a%4==0:
    #     a=a//2
    #     ans+=1
    #     continue
    elif a%2==0:
        a=a//2
        ans+=1
        continue
    else:
        a-=1
        ans+=1
        continue
print(ans)

# 반례 28

이렇게 제출했는데 당연하게도 빨랐지만 7퍼센트에서 틀렸습니다가 떳다

이 문제는 단순해보이지만 그렇게 단순하지않다

3으로 나누는게 가장 효율적인방법이니까 2로 나눌수있는것도 3으로 나누면 될까?

 

이방법은 10에서는 정론이고

1024에서는 아니다

 

아쉽게도 모든 경우의 수에 적용가능한 수학적인 방법이 도저히 생각나지않아

 

답을본다

https://hongcoding.tistory.com/46

n = int(input())

dp = [0] * (n+1)

for i in range(2, n+1):
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])

동적계획법을 이용하셨고

정말로 1부터 n까지 모든수의 최소횟수를 구했다 

 

디폴트는 dp[i]는 dp[i-1]보다 1회더많은 수이다

만약 2나 3으로 나눠떨어진다면

dp[i//2]+1과 dp[i//3]+1, dp[i-1]+1 중에 가장 최저값을 

dp[i]값으로 갖는다

 

이렇게해서 만들어진 최소값들은 정말 납득할수있었다

 

n까지의 최소값을 구하고싶다면

1부터 확실한 최소값들을 쌓아나간다

왜 이생각을 못했을까

 

지금은 이렇게 알고리즘별로 분류가 되있는 문제들만 풀고있어서

어떤 알고리즘을 적용할지 생각할 필요가없지만

나중에는 그것도 첨에 고려해봐야될것같다

 

지금드는 생각인데 모든 문제를 다 동적계획법으로 풀수있을것같다 아니겠지?

n-queen이나 스도쿠같은 완전계획법문제들도 말이다 

아니다 그것들은 안될것같다 경우의수가 너무 많으니 말이다

 

쨋든 다음문제는 잘 풀수있길바라며