[프로그래머스] 숫자 변환하기

1. 문제

숫자 변환하기

2. 개요

자연수 x를 y로 변환하려고 한다.

사용할 수 있는 연산은 총 세 가지로 다음과 같다.

x에 2를 곱하기,

x에 3을 곱하기,

x에 n을 더하기.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환할 수 있는 최소 연산 횟수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

최댓값까지의 연산 횟수를 모두 저장할 수 있는 크기의 배열 cnt를 만들어두고 모든 원소의 값들을 최댓값으로 초기화해둔다.

x부터 연산을 시작하므로 cnt[x] = 0으로 초기화한다.

x부터 값을 1씩 늘려가며 탐색한다.

각 연산 결과값이 범위 내이고 배열에 저장된 연산횟수의 값이 현재값의 연산횟수보다 크지 않다면

해당 위치의 연산횟수를 현재까지의 현산횟수 + 1로 저장한다.

끝 값까지 탐색을 완료했다면 cnt[y]의 값을 확인한다.

초기에 저장해둔 최댓값이라면 연산이 불가능하므로 -1을 출력하고, 그렇지 않다면 그대로 cnt[y]의 값을 출력한다.

3-2. C#

using System;

public class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;

        int[] cnt = new int[1000001];
        Array.Fill(cnt, int.MaxValue);
        cnt[x] = 0;

        for (int i = x; i < 1000001; i++)
        {
            if (i * 2 < 1000001 && cnt[i * 2] > cnt[i])
                cnt[i * 2] = cnt[i] + 1;

            if (i * 3 < 1000001 && cnt[i * 3] > cnt[i])
                cnt[i * 3] = cnt[i] + 1;

            if (i + n < 1000001 && cnt[i + n] > cnt[i])
                cnt[i + n] = cnt[i] + 1;
        }

        answer = cnt[y] == int.MaxValue ? -1 : cnt[y];

        return answer;
    }
}