Dynamic Programing - 1463

백준 온라인 코딩 문제풀이

https://www.acmicpc.net/

Baekjoon Online Judge

---

1로 만들기 문제

 

알고리즘 관련 공부를 안했어서 DP 문제의 접근법을 이번에 새로 알게 되었다.

 

DP 알고리즘은 Top-Down(하향식) 방식과 Bottom-Up(상향식) 방식으로 크게 2가지가 존재한다.

 

DP 문제로 유명한 것은 특정 정수를 최소 횟수로 만들기(이 문제)와 피보나치 수열, 배낭 문제, 최장 공통부분 수열 등이 있다고 한다.(GPT로 공부하며 예시를 받았음)

 

또한 장단점은 다음과 같다고 한다.

장점
1. 중복 계산을 방지하여 효율성을 극대화.

2. 최적화 문제가 많아 코딩 테스트에서 자주 활용됨.

단점
1. 점화식을 도출하기 어려운 경우가 있음.

2. 메모리 사용량이 많아질 수 있음.

 

이 문제의 경우 작은 문제를 먼저 해결한 후 점차 수를 키워나가는 방식으로 진행하게 된다.

 

다시 말해 상향식의 문제이다.

 

우선 코드부터 보면서 설명하겠다.

 

코드

using System;
//using System.Linq;
//using System.Collections.Generic;
namespace StudyCS
{
    class Program
    {
        public static void Main(string[] args)
        {
            int x = int.Parse(Console.ReadLine());
            Console.WriteLine(DP(x));
        }
        public static int DP(int _x)
        {
            int[] dp = new int[_x + 1];

            for(int i = 2; i <= _x; i++)
            {
                dp[i] = dp[i - 1] + 1;

                if (i % 2 == 0) dp[i] = Math.Min(dp[i], dp[i / 2] + 1);
                if (i % 3 == 0) dp[i] = Math.Min(dp[i], dp[i / 3] + 1);
            }
            return dp[_x];
        }
    }
}

이 문제에서 반복되는 최대 횟수는 1씩 정수의 수만큼 반복되는 것이 가장 큰 횟수이다.

즉, 반복문의 수가 최소 입력 수인 2부터 입력 받은 정수인 x까지 반복된다.

 

그리고 각 반복에서 dp[i] = dp[i-1] + 1을 기본적으로 할당한다.(횟수 1회 증가)

이후 현재 값(i)이 만약 2나 3으로 나눠진다면 나눈 후 1회를 더하는 것과 현재 가지고 있는 값을 비교한 후 더 적은 횟수인 것을 저장하게 된다.

 

이런식으로 상향식을 돌리다 보면 원하는 값인 x값에 도달하였을 때 최소 횟수를 찾을 수 있게 된다.