[Lv.2] 숫자 변환하기 [프로그래머스_코딩테스트] [DP, BFS] [35분]

🔍 문제 요약

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

x에서 y로 값을 만드는 방법을 할 때 3가지 방법으로 섞어서 만드려고 한다. 이 때 최소한의 횟수로 만들 수 있는 것을 구하는 문제. 3가지 방법은 (+n, x2, x3)이다.

🧠 나의 접근 방식과 시행착오

간과한 부분이 있었다. 곱하기끼리는 순서가 상관이 없지만 더하기를 하고 곱하기를 하는 등의 작업이 섞이게 되면 문제가 있다는 것을 놓쳐서 문제를 반절은 맞고 반절은 틀리는 형태가 되었다. (맞은 건 운 좋게 테스트 케이스가 순서대로 동작한 것으로 보인다) 틀린 문제 풀이 방법은 아래와 같이 그냥 3중 for문을 돌렸던 것.. 문제를 적을때부터 BFS 방식이라는 것은 알았지만 구현에 익숙치 않았던 점에서 공부가 필요할 것으로 보인다.

using System;

public class Solution
{
    /// <summary>
    /// 숫자 변환하기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/154538
    /// </summary>
    public int solution(int x, int y, int n)
    {
        int answer = -1;
        int count = int.MaxValue;
        
        for (int i = x, iCount = 0; i <= y; i += n, iCount++)
        {
            for (int j = i, jCount = 0; j <= y; j *= 2, jCount++)
            {
                for (int k = j, kCount = 0; k <= y; k *= 3, kCount++)
                {
                    if (k != y) continue;
                    int sumCount = iCount + jCount + kCount;

                    if (count > sumCount)
                    {
                        count = sumCount;
                    }
                        
                    break;
                }
            }
        }

        if (count < int.MaxValue)
        {
            answer = count;
        }
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var xyn1 = new[] { 10, 40, 5 };
        var xyn2 = new[] { 10, 40, 30 };
        var xyn3 = new[] { 2, 5, 4 };

        Console.WriteLine(sl.solution(xyn1[0], xyn1[1], xyn1[2]));
        Console.WriteLine(sl.solution(xyn2[0], xyn2[1], xyn2[2]));
        Console.WriteLine(sl.solution(xyn3[0], xyn3[1], xyn3[2]));
    }
}

✅ 풀이 코드

BFS를 활용하여 문제를 푼 풀이 코드. 아래의 코드와 설명을 보면서 익숙해져보자.

 

• dist[i]는 x에서 i까지 도달하는 데 필요한 최소 연산 횟수
• BFS 방식이기 때문에 가장 빠른 연산 순서를 먼저 만나면 거기서 종료, 즉 최소 연산 횟수 확보 가능
• 한 번 방문한 숫자는 다시 방문하지 않음 → 불필요한 중복 탐색 방지

 

using System;
using System.Collections.Generic;

public class Solution
{
    public int solution(int x, int y, int n)
    {
        int[] dist = new int[y + 1];
        Array.Fill(dist, -1);
        dist[x] = 0;

        Queue<int> q = new Queue<int>();
        q.Enqueue(x);

        while (q.Count > 0)
        {
            int cur = q.Dequeue();

            foreach (int next in new[] { cur + n, cur * 2, cur * 3 })
            {
                if (next > y || dist[next] != -1) continue;

                dist[next] = dist[cur] + 1;
                q.Enqueue(next);
            }
        }

        return dist[y];
    }
}

🔄 정리

BFS의 로직에 대해서 핵심 정리만 한 스크린샷을 토대로 학습을 해두고 다음 번 문제에 적용을 해보자.