[백준] 1463번 (python 파이썬)

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

1463번: 1로 만들기

 

나의 첫 DP (다이나믹 프로그래밍) 문제이다.

아니나 다를까 익숙하지 못해 그런지 어렵다.

첫 시작부터 어떻게 해야 할지 감이 안온다.

 

DP에 관한 여러 내용을 읽어보았다.

 

읽고 나름 정리를 해보았다.

먼저 DP를 적용하기 위해선 다음과 같은 조건이 필요하다

• 부분 반복 문제
• 최적 부분 구조

* 부분 반복 문제 : 문제를 여러 개의 하위 문제(subproblem)로 나누어 풀 수 있다.

예) 피보나치 수열 f(n) = f(n-1) + f(n-2)

* 최적 부분 구조 : 풀고자 하는 문제의 최적의 답은 하위 문제들의 최적의 답으로 얻을 수 있다.

예) f(n) = f(n/2) + 1 이고 가장 작은 f(n)을 구하는 문제를 풀고자 한다.

f(n/2)의 값으로 10과 20이 있다면 f(n/2)의 최적의 값은 10이고 f(n)은 21이 아닌 11이 된다.

 

DP를 풀기위한 기법으로는 메모이제이션이 있다.

위의 피보나치 수열을 예로 들면, 반복되는 계산이 있다. fib(5)는 두번반복된다.

반복한다는 것은 결국 성능을 떨어뜨리게 되므로 좋지 않다.

만약 첫번째로 계산했을때 미리 값을 저장해 놓았다가 두번째로 만나면 계산하지 말고 저장한 값에 접근해서 사용하면 더욱 속도가 빨라진다. 이 개념이 바로 캐쉬이다.

 

나올 수 있는 모든 값들의 크기만큼 배열을 만들어 놓고

특정 값이 나올때 마다 해당 인데스에 해당하는 값을 할당한다.

 

접근 하는 방식으로는 2가지가 있다.

• top - down 방식
• bottom - up 방식

다음은 피보나치 수열의 top - down 방식으로 접근한 코드이다.

// 최대 범위 10보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
memo = [0] * 11

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
def fib(n):
  if memo[n] != 0:
    return memo[n]
  memo[n] = fib(n-1) + fib(n-2)
  return memo[n]

위와 같이 top - down 방식은 재귀함수를 사용한다.

 

다음은 피보나치 수열의 bottom - up 방식으로 접근한 코드이다.

// 최대 범위 N보다 1 크게 사용.
// memo[0] 초기값 상태 0으로 비워둘것임.
memo = [0] * 11

memo[1] = 1;
memo[2] = 1;

// 메소드로 표현한 피보나치 수열
def fib(n):
  for i in range(3, len(memo)):
    memo[i] = memo[i-1] + memo[i-2]
  return memo[n]

위와 같이 bottom - up 방식은 for문을 사용한다.

 

자, 이제 대략적인 DP의 개념을 알았으므로 본래의 문제를 풀어보자.

 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
    1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
    2. X가 2로 나누어 떨어지면, 2로 나눈다.
    3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다.
연산을 사용하는 횟수의 최솟값을 출력하시오.

 

어떤 수가 주어질때 1을 빼는 것 보다 나눌 수 만 있다면 2 또는 3으로 나누는게 1로 도달하는 데에 더 빠를 것 같다.

만약 그렇다면 이 문제는 그리디 문제로 볼 수 있다.

항상 3으로 나눠보고 안되면 2로 나눠보고 그것도 안되면 마지막으로 1을 빼는게 최적의 해이기 때문이다.

하지만 10의 경우를 생각해보자.

 

(그리디 해법) 10 -> 5 -> 4 -> 2 -> 1  : 5번

(반례) 10 -> 9 -> 3 -> 1  : 4번

 

즉, 그리디 문제가 아닌 모든 경우를 짚어봐야 하는 DP 문제이다.

DP가 성립되기 위한 2가지 조건이 있다고 했다.

 

* 부분 반복 구조 :

입력값이 N일 때의 횟수는 

N-1일때의 횟수 + 1 또는 (2의 배수일때) N//2 일때의 횟수 + 1 또는 (3의 배수일 때) N//3일때의 횟수 + 1이다.

* 최적 부분 구조:

입력값이 N일 때의 횟수는

N-1일때의 횟수 + 1 와 (2의 배수일때) N//2 일때의 횟수 + 1 와 (3의 배수일 때) N//3일때의 횟수 + 1 중에 가장 작은 수이다.

 

2가지 조건을 만족 했으므로 DP임을 깨닫고

N+1만큼 길이를 가진 배열 arr (캐쉬)를 만든후,

2가지 접근방식중 한가지를 선택해보자.

 

arr = [0] * (N + 1)

 

현재 가장 빨리 알 수 있는 정보로는

 

arr[1] = 0

arr[2] = 1

arr[3] = 1

 

가 있다.

즉, 배열의 밑부분의 값들을 알고 있다.

bottom - up 방식이 유리하다.

bottom - up 방식은 for문을 사용한다고 했다.

천천히 생각해보자.

 

4의 횟수가 될 수 있는 방법으로는

1. 3일때의 횟수 + 1

2. 2(4//2)일때의 횟수 + 1

가 있고 그 중, 제일 작은 값을 가진다.

 

arr[4] = min(arr[3], arr[4//2]) + 1

 

5의 횟수가 될 수 있는 방법으로는

1. 4일때의 횟수 + 1

만 있다.

 

arr[5] = arr[4] + 1

 

6의 횟수가 될 수 있는 방법으로는

1. 5일때의 횟수 + 1

2. 3(6//2)일때의 횟수 + 1

3. 2(6//3)일때의 횟수 + 1

가 있고 그 중, 제일 작은 값을 가진다.

 

arr[6] = min(arr[5], arr[6//2], arr[6//3]) + 1

 

이렇게 코드가 반복된다.

number = int(input())
cache = [0] * (number+1)

cache[2] = 1	# 이 부분은 삭제해야 한다.
cache[3] = 1	# 이 부분은 삭제해야 한다.

for i in range(4, number + 1):	# 4가 아닌 2로 수정해야 한다.
  cache[i] = cache[i-1] + 1
  if i % 2 == 0:
    cache[i] = min(cache[i], cache[i//2] + 1) 
  if i % 3 == 0:
    cache[i] = min(cache[i], cache[i//3] + 1) 
print(cache[number])

위의 코드에선 배열 이름을 cache로 했다.

아까 우리가 미리 생각으로 cache[1]과 cache[2]와 cache[3]을 계산했다.

위의 코드에서 2와 3의 횟수를 리터럴로 바로 할당했다.

 

그런데 이 문제의 입력 범위를 보면 1이상 백만 미만의 정수이다.

즉, 1을 넣으면 그만큼의 배열(캐쉬)공간이 만들어 질 것이고 인덱스 2와 3의 접근은 인덱스 에러가 난다.

따라서 2와 3도 리터럴로 할당하는게 아니라 반복문의 계산을 통해 자동으로 할당하게 한다.

number = int(input())
cache = [0] * (number+1)

for i in range(2, number + 1):
  cache[i] = cache[i-1] + 1
  if i % 2 == 0:
    cache[i] = min(cache[i], cache[i//2] + 1) 
  if i % 3 == 0:
    cache[i] = min(cache[i], cache[i//3] + 1) 
print(cache[number])