#백준 1463번 #파이썬 #알고리즘 #문이과통합중

### 문제설명 

 

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

# X가 3으로 나누어 떨어지면, 3으로 나눈다.

# X가 2로 나누어 떨어지면, 2로 나눈다.

# 1을 뺀다.

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

 

### 제약조건 

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

 

### 예제입력 

10

### 예제출력

3

 

### 문제해석 

다이나믹 프로그래밍 문제. 문제를 해석하고 N 을 1~3까지 고정값으로 정해보면은 [0,1,1] 후에 N 에 4이상을 대입해보면은

DP[n] = DP[n-1] + 1 

DP[n] = DP[n//3] + 1

DP[n] = DP[n//2] + 1

3가지 메인 패턴을 정해줄 수 있다. 

 

if 문으로 각 패턴이 정해지는 조건을 잡아주고. n % 3 ==0, n % 2 ==0 ..

예외케이스 ex) 10 과 같은 경우를 가정해서 추가적인 조건을 더해준다. 

 

메인패턴 => input 테스트 

 

예외케이스 발생 => 패턴삽입가능 ? 가능 => 메인패턴, 불가능 => 예외처리 

 

### 점화식  

dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1

 

### 문제풀이1 

 

몇번의 수정끝에.. 아래와 같이 작성.. 틀렸다고 나오는데.. 솔직히 왜틀렸는지 모르겠다.. ^^ 

X = int(input())
DP = list([0 for _ in range(X+3)])

DP[0] = 0 
DP[1] = 0
DP[2] = 1
DP[3] = 1

for n in range(4,X+1):
  
  DP[n] = DP[n-1] + 1

  if n % 3 == 0:
    if DP[int(n)] > DP[n//3] + 1  :
      DP[n] = DP[n//3] + 1
    else:
      DP[n] = DP[int(n-1)] + 1 


  elif n % 2 == 0:    
    if DP[int(n)] > DP[n//2] + 1  :
      DP[n] = DP[n//2] + 1
    else:  
      DP[n] = DP[int(n-1)] + 1
 

print(DP[X])
print(DP[:X])

 

### 문제풀이 2

 

블로그에서 퍼온 풀이. 접근법은 맞는데.. if, else 구조때문에.. ? 

n = int(input())

dp = [0 for _ in range(n+1)]

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

    if i%3 == 0 and dp[i] > dp[i//3] + 1 :
        dp[i] = dp[i//3] + 1


    if i%2 == 0 and dp[i] > dp[i//2] + 1 :
        dp[i] = dp[i//2]+1
      

print(dp[n])
print(dp[:n])