[BAEKJOON] 1로 만들기 - python

1로 만들기

알고리즘 - dynamic programming

 

과정:

처음에는 3으로 나눠질 수 있는 숫자는 3으로 나누기 -> 2로 나눠질 수 있는 숫자는 2로 나누기 -> 둘다 안되면 -1 로 풀어보려했지만 힌트를 보고 아닌것을 알게되었다.

위와 같이 풀면 10 -> 5 -> 4 -> 2 -> 1 4번으로 더 연산이 많이 필요해진다.

힌트를 참고하면

X=10 : 10 -> 9 -> 3 -> 1

X=9 : 9 -> 3 -> 1

X=3 : 3 -> 1

형태가 된다.

n : 입력받은 정수 N
arr[n] : 연산하는 횟수
arr[i-1] +1 : 1을 뺀다 연산
arr[i//3] +1 : 3으로 나누는 연산
arr[i//2] +1 : 2로 나누는 연산

'1을 뺀다 연산', '3으로 나누는 연산', '2로 나누는 연산' 을 적절히 사용하여 연산을 하는 횟수의 최소값을 선택하도록 작성하였다

n = int(input())
arr = [0]*(n+1) //array 0으로 초기화

for i in range(2,n+1): 
  arr[i] = arr[i-1] + 1 #1을 뺀다 : i-1로 연산을 1번했기때문에 횟수+1을 해줌
  if i%3 == 0: 
    arr[i] = min(arr[i],arr[i//3]+1) #3으로 나눈다 : 1을 빼는 방법과 3으로 나누는 방법중 횟수가 적은 것을 선택
  if i%2 == 0: 
    arr[i] = min(arr[i],arr[i//2]+1) #2로 나눈다: 1을 빼는 방법과 2로 나누는 방법중 횟수가 적은 것을 선택

print(arr[n])

 

arr[0] = 0

arr[1] = 0

arr[2] = 1 (2 -> 1)

arr[3] = 1 (3 -> 1)

arr[4] = 2 (4 -> 2 -> 1 or 4 -> 3 -> 1)

arr[5] = 3 (5 -> 4 -> 2 -> 1)

...