[이코테] 다이나믹 프로그래밍_1로 만들기

문제설명

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.

1. X가 5로 나누어 떨어지면 5로 나눈다.
2. X가 3으로 나누어 떨어지면 3으로 나눈다.
3. X가 2로 나누어 떨어지면 2로 나눈다.
4. X에서 1을 뺀다.

정수가 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오

입력조건

• 첫째 줄에 정수 X가 주어진다.(1 <= X <= 30,000)

출력조건

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

---

 

 

풀이

- 최적 부분 구조 & 중복되는 부분 문제를 만족한다 

-> DP 조건 만족!

 

점화식

- a[i] = i 를 1로 만들기위한 최소 연산 횟수.

- 1을 빼는 연산을 제외하고는 해당 수(2 or 3 or 5)로 나누어질 때에 한해서만 점화식이 적용된다.

 

Python 코드

x = int(input())
# DP 테이블
table = [0] * 30001

for i in range(2, x+1):
    # 1을 뺐을 경우
    table[i] = table[i-1] + 1
    # 2와 나누어 떨어질 경우 & 1을 뺏을 경우 비교
    if i % 2 == 0:
        table[i] = min(table[i], table[i//2] + 1)
    # 3과 나누어 떨어질 경우 & 직전 비교
    if i % 3 == 0:
        table[i] = min(table[i], table[i//3] + 1)
    # 5와 나누어 떨어질 경우 & 직전 비교
    if i % 5 == 0:
        table[i] = min(table[i], table[i//5] + 1)
print(table[x])

- 공배수가 존재하여 if 대신 elif 사용은 안된다.

- bottom up으로 작은 수 부터 목표 수 x까지 차례대로 도달한다. (+1 필수!!!)

- 바로 앞의 DP 테이블 값을 먼저 최적값 할당 후 각각의 나누어 떨어지는 경우와 min으로 계속 비교하여 최적값을 할당한다.

 

 

나의 처음 더러운 풀이..

N =int(input())

arr = [0] * (N+1)
arr[1] = 0
arr[2] = 1
arr[3] = 1
arr[4] = 2
arr[5] = 1

decimal=[5] # 소수 담는 리스트

def getMyDivisor(n): #n의 약수 구하기

    divisorsList = []

    for i in range(1, int(n**(1/2)) + 1):
        if (n % i == 0):
            divisorsList.append(i) 
            if ( (i**2) != n) : 
                divisorsList.append(n // i)

    divisorsList.sort()
    
    return divisorsList

for i in range(6, N+1):
  arr2 = getMyDivisor(i)

  idx = len(arr2) // 2
  if len(arr2) == 2: #소수일 때 
    min = arr[decimal[-1]]+(i-decimal[-1])

    for d in range(decimal[-1],i): #자기 자신을 제외한 소수들 중 가장 큰 소수부터 비교
      if arr[d]+i-d < min:
        min=arr[d]+i-d
      
    arr[i] = min

  elif len(arr2) % 2 ==1: #제곱근 일 때
    arr[i] = arr[arr2[idx]] * 2
  else: #그 외의 경우
    min = arr[i-1]+1 #i의 직전 dp 테이블 값
    temp = arr[arr2[idx-1]] + arr[arr2[idx]] #i의 약수에 해당하는 dp 테이블 값의 합
    if min < temp:
      arr[i] = min
    else:
      arr[i] = temp

print(arr[N])

문제점

1. 불필요한 약수 구하기 

2. 소수일 때, 제곱근 일 때, 그 외로 나누어서 계산

 

구현하고 많이 다듬어보기........!!!!