알고리즘 백준 1463 1로 만들기(파이썬)

알고리즘 백준 1463 1로 만들기(파이썬)

백준 1로 만들기 파이썬

백준 파이썬 1로 만들기

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

코드

if __name__ == '__main__':
    import sys
    N = int(sys.stdin.readline())
    count=[0]*(N+3)
    count[1]=0
    count[2]=1
    count[3]=1
    for i in range(4,N+1):     #1)
        number=10**6
        if i%3==0:
            number = count[i//3]
        if i%2==0:
            number = min(count[i//2],number)
        count[i] = min(count[i-1],number)+1
    print(count[N])

 

문제설명

0) 그리디 알고리즘은 처음 생각한 방법이 반례없이 적용될때 사용하며 동적계획법은 모든 경우의 수 중에서 최솟값을 찾는다

0-1) 그리디 알고리즘으로 풀경우 10을 큰수로 나누지만 반례가 존재하기때문에 동적계획법으로 풀어야한다고 한다

 

0-2) 구현은 비효울적인 방법같기는한데 다른방법이 생각이 안나서

       N까지 for문으로 계산하는 최소수를 다 저장시킨다

       6이 들어오면 3으로 나누어떨어지므로 최솟값을 저장한 리스트에서 2의(6나누기3)최솟값을 찾아 +1 해주면된다

       7같은것이 들어오면 3과 2로 안나누어떨어지므로 전의수인 6의 최솟값을 찾아 +1해준다

 

1) #1)코드는 N까지 돌며 가장 큰수인 3으로 나누어 떨어지나 확인하며 그다음은 2를 확인하며 나누어 떨어지지 않을 경우 전의 수의 최솟값에서 +1 해주는 코드이다.

 

 

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main