백준 1463 - 1로 만들기

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

1463번: 1로 만들기

우르누ㅏㅓ룬아ㅜㄹ나ㅣㅜㄹ나ㅣㅜ

dp계속 못 푸는중,, 

코테볼라믄 이 dp를 뿌셔야되는데 내가 뿌셔지고 잇네..

 

이 문제는 진짜 단순히 어떤 수를 입력받아서 1로 만들어야되는데 1로 만들 때 필요한 연산의 최소 횟수를 구하는 문제이다. 연산은 1을 빼기, 2로 나누기, 3으로 나누기 이렇게 세 종류가 있다.

너무 문제가 단순해서 오히려 더 규칙을 찾아 알고리즘화하는 것이 어려운 것 같다.

그래서 다른 분의 풀이 코드를 참고했다.

https://seongonion.tistory.com/40

[백준] 1463번 1로 만들기 - 파이썬(Python)

이 포스팅을 참고 했는데 다른 포스팅들보다 더 자세하게 풀이 되어 있어서 이해하는데 많은 도움을 받았다.

 

 

그럼 정답 코드를 리뷰해보자.

풀이 코드)

x = int(input())
dp = [0] * (x+1)
dp[1] = 0

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

    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[x])

여기서 dp배열을 x+1의 크기만큼 선언 후 초기화했는데

dp에는 각 수를 1로 만들기 위해 걸리는 최소 연산횟수를 저장한다.

 

dp[1] = 1을 1로 만들기 위해 필요한 최소 연산 횟수 => 0

dp[2] = 2를 1로 만들기 위해 필요한 최소 연산 횟수 => 1 

dp[3] = 3을 1로 만들기 위해 필요한 최소 연산 횟수 => 1

 

처음에는 큰 수일 경우, 2보다는 3으로 나눠주어야 수가 더 작아지므로 3으로 나눠떨어지거나 3보다 1이 클 경우엔 1을 빼서 무조건 3으로 나누어주려고 했었다. 하지만, 이는 그냥 순간의 최선의 선택을 하는 그리디 알고리즘이고, 이 문제는 순간순간마다 최선의 선택을 한다고 해도 원하는 최종 결과값을 얻지 못한다.

 

즉, dp를 통해 모든 케이스(1을 빼거나/2로 나누거나/3으로 나누거나)를 다 해보아야한다는 소리이다.

 

dp[6]을 구하기 위해서는 3가지 경우가 존재한다.

설명의 편의성을 위해 

dp[4] = 2 , dp[5] = 3 을 구해놓고 설명하도록 하겠다.

 

1. 1을 빼는 연산을 했을 경우

1을 빼면 5가 된다. 그럼 5를 1로 만들기 위해 필요한 최소연산의 횟수 + 1을 해주면 된다.

+1을 하는 이유는 1을 빼는 연산을 했으니 그 연산에 대한 횟수를 올려주기 위함이다.

dp[6] = dp[5] + 1 ==> dp[i] = dp[i-1] + 1

dp[6] = 3 + 1 = 4

 

2. 2로 나누는 연산을 했을 경우

2로 나누면 3이 된다. 그럼 3을 1로 만들기 위해 필요한 최소연산의 횟수 +1을 해주면 된다.

+1을 하는 이유는 2로 나누는 연산을 했으니 그 연산에 대한 횟수를 올려주기 위함이다.

dp[6] = dp[3] + 1  ==> dp[i] = dp[i//2] + 1

dp[6] = 1 + 1 = 2

 

3. 3으로 나누는 연산을 했을 경우

3으로 나누면 2가 된다. 그럼 2를 1로 만들기 위해 필요한 최소연산의 횟수 +1을 해주면 된다.

+1을 하는 이유는 2로 나누는 연산을 했으니 그 연산에 대한 횟수를 올려주기 위함이다.

dp[6] = dp[2] + 1  ==> dp[i] = dp[i//3] + 1

dp[6] = 1 + 1 = 2

 

이렇게 dp[6]는 3가지 경우로 구할 수 있고, 이 문제에서는 가장 최소 횟수를 구하면 되므로 위 3가지 경우 중에서 가장 작은 값만 dp[6]에 저장해주면 된다. 따라서, dp[6] = 2가 된다.

이러한 알고리즘은 위의 풀이코드 반복문 안에 구현되어 있다.

 

마지막엔 숫자 x의 최소 연산 횟수만 출력하면 되므로, dp[x]를 출력해주면 된다.