[백준 1463번] 1로 만들기 - 동적 계획법

 

# 어렵다... 아이디어를 짜내려하는데 참 어렵다..

 

처음 이 문제를 보고 풀이 방법을 생각해보는데 너무 복잡하여 마땅한 해결방법을 찾지 못했다. 

따라서 일단은 작은 수부터 어떤식으로 1을 만들 수 있을지를 계산해 보았다.

# 1
# 2 1
# 3 1
# 4 3 1, 4 2 1
# 5 4 2 1 ,5 4 3 1
# 6 2 1
# 7 6 2 1
# 8 4 2 1
# 9 3 1
# 10 9 3 1
# 11 10 9 3 1
# 12 4 2 1
# 13 12 4 2 1
# 14 7 6 2 1
# 15 5 4 2 1
# 16 8 4 2 1
# 17 16 8 4 2 1
# 17 16 15 5 4 2 1

이런 식으로 최소한의 경우로 1을 만들 수 있겠구나 하는 생각이 들었고 최대한 규칙을 찾아보았다.

1. 3의 제곱수인 경우에는 3으로 계속 나누어준다.

2. 2의 제곱수인 경우에는 2로 계속 나누어준다.

3. 1을 뺐을 때 3의 배수인 경우에는 우선 1을 빼주고 3으로 나누어준다.

4. 1을 더했을 때 6의 배수인 경우에는...?

5. 모든 수는 2, 3, 5와 소수의 배수로 찾아줄 수 있나? 그럼 소수인 경우에는 먼저 1을 빼고 계산해주면 되나??

 

이런식으로 생각을 계속 하다보니 머리속에서 생각의 의사결정 나무가 depth 제한 없이 밑으로 내려갔다.

이게 맞나..? 이게 맞나..? 하는 스스로 의심이 들었고 알고리즘 파악에 너무 많은 시간을 투자하고 싶지 않아 구글링을 시도했다.

( 딱 봐도 몇시간씩 걸릴 것을 하루종일 잡고 알고리즘을 고민하는게 도움이 되는지를 잘 모르겠다... )

 

구글링을 한 결과 이 문제는 동적 계획법 ( Dynamic Programming ) , 줄여서 DP 를 활용해 푸는 문제임을 알 수 있었다.

들어는 보았지만 아직 풀어본적 없는 문제이기 때문에 뭔가 설레는 마음이 들어 좋았달까..

 

-- 동적 계획법

 

동적 계획법이란 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법을 말한다. 

 

주어진 문제를 풀기 위해서 문제를 여러개의 하위 문제로 나누어 푼다음, 그것을 결합하여 최종적인 목적에 도달한다고 한다. ( RandomForest의 샘플링이 생각난다.. )

주로 최단 경로, 행렬의 제곱문제 등에 사용된다. ( 대표적인 예시로 재귀함수인 피보나치 수열이 있다 )

 

=> 재귀적인 구조를 활용할 수 있는 점화식을 찾는것이 핵심!

 

언제 DP를 사용할 수 있을까? : 특정 데이터 내 최대화 / 최소화 계산 OR 데이터 개수 세기, 확률 계산 등

DP를 사용할 준비 : 문제 변수 파악 ( 변수 개수 ) 

 

보통 DP문제는 Bottom-up의 상향 방식과, Top-Down의 하향 방식으로 나뉜다.

상향 방식은 주로 반복문을 사용하고 하향 방식은 재귀문을 사용해서 문제를 해결한다.

 

1. 상향 방식

- 배열이 존재할 때 0번째부터 점화식을 만들어 반복문을 통해 n번째까지의 결과를 구하는 방법

( 결과값을 기억하고, 값을 다시 사용한다 )

 

2. 하향 방식

- n번째의 결과를 구하기 위해 위에서 먼저 함수를 호출하고 함수를 재귀하여 0번째의 값까지를 구하는 방법

 

# 동적 계획법은 가능한 모든 방법을 고려하기 때문에 이러한 단점을 극복하기 위해 그리디 알고리즘이 등장했다.

 

-----------------------------------------------------------------------------------------------------------------------------------

 

자 그럼 다시 문제로 돌아가보자

동적 계획법을 찾아보고 나니 처음 내가 수동으로 구했던 1을 만들었던 방법이 더 큰 수에서는 작은 수의 방법을 재사용한다는 규칙을 찾아낼 수 있었다. 결국 작은 숫자에서 구한 방법을 저장하였다가 큰 숫자에서 사용해주면 되겠구나!! 

 

 

문제에서 숫자를 1로 만들기 위해 주어진 방법은 3가지였다.

1. 3으로 나눈다.

2. 2로 나눈다.

3. 1을 뺀다.

 

기존 값을 기억해주기 위해 DP배열을 만들어주고, 2부터 반복해서 배열을 만들어주자.

n = int(input()) # 입력받는 숫자

dp = [0] * (n+1) # 인덱스 0은 무시하려고 n+1개를 만들어주었다.

for i in range(2,n+1): # 어차피 1은 0번이기 때문에 반복을 안해주어도 된다.
    dp[i] = dp[i-1] + 1
    if i%3==0:
        # 이미 1을 더해주었기 때문에 1을 빼고 시작하기 or 3을 나누고 시작하기 중 짧은 횟수 찾기
        dp[i] = min(dp[i], dp[i//3]+1)
    if i%2==0:
        # 이미 1을 더해주었기 때문에 1을 빼고 시작하기 or 2를 나누고 시작하기 중 짧은 횟수 찾기
        dp[i] = min(dp[i], dp[i//2]+1)
    # 6의 배수일 수 있기 때문에 위의 경우를 둘다 확인해 4가지의 경우 중 가장 작은 경우의 수를 찾는 것!!
print(dp[n])

처음 경우의 수를 세보며 생각했던 걸 생각하면 코드가 너무나도 짧다.. 처음 생각대로 코드를 만들었다면 20개의 if문 정도는 사용해야 했을듯..? 0부터 방법을 확인해준 bottom-up 방법이라 반복문을 통해 구현해 줄 수 있었다.

 

이번이 처음으로 DP문제를 접한 것이라 이해하는데 많은 시간을 들였다. 본래 재귀함수를 공부할 때 하노이 탑 하나 이해하는데에도 많은 시간이 들었던 것을 생각하면 앞으로의 어려운 문제들이 무서워진다.. ( 사실 하노이탑 지금 다시 하면 한번에 딱 결과 낼 수 있을지 확신은 못한다 ㅎㅎ.. ) 

 

그래도 이제 좀 알고리즘을 배운다는 느낌?? ㅎㅎ

 

 

오늘도 성공적으로 숫자들을 1로 만들어주었다