1463번 1로 만들기

문제 보러가기

🅰 설계

• 문제에서 주어진 아래의 조건에 맞추어 코드를 구현하고 카운트의 최솟값을 구하는 알고리즘을 실행시켰지만 답이 나오지 않았다…

  1. x가 3으로 나누어 떨어지면, 3으로 나눈다.

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

  3. 1을 뺀다.

• 다음으로 연필로 써내려가면서 규칙이 있나 찾아보았다. 개인적으로 싫어하는 방법이지만 풀 방법이 생각나지 않아 도전해 보았다…

  역시, 규칙은 보이지 않았다…

✔ 정답 코드 구글링

N = int(input())
dp_list = [0,0,1,1] # 0 ,1, 2, 3 의 최소 수 미리 저장

for i in range(4, N + 1) :
    # 먼저 1을 뺏을 경우 나오는 경우의 수 저장
    dp_list.append(dp_list[i-1] + 1)

    #2로 나누어질 경우 기존 1을 뺏을 경우의 수와 비교하여 최솟값 저장
    if i % 2 == 0 :
        dp_list[i] = min(dp_list[i], dp_list[i//2] + 1)

    #3으로 나누어질 경우 기존 1을 뺏을 경우의 수와 비교하여 최솟값 저장
    #여기서 2 또는 3으로 나누어질 경우 모든 경우를 봐야하므로 elif가 아닌 if로 설정
    if i % 3 == 0 :
        dp_list[i] = min(dp_list[i], dp_list[i//3] + 1)

print(dp_list[-1])

✅ 후기

• 1로 만들기문제는 큰 문제를 작은 문제로 단순화시켜 해결하는 다이나믹 프로그래밍문제이다.

  따라서 어떤 수 N에 대하여 최소 경우를 알고 싶다면 기본이 되는 점화식을 만들어야 한다.

  본 문제에서는 dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1으로 점화식을 만들 수 있다.

• N-1로 시작한 경우, N//2로 시작한 경우, N//3으로 시작한 경우, 각각의 경우의 수를 찾아 최소 경우의 수를 찾으면 되는 일이다.

• 점화식으로 풀어나가는 DP문제는 익숙치 않아서 어려운 것 같다…💦