[level 2] 숫자 변환하기 - 154538

문제 링크

성능 요약

메모리: 88.1 MB, 시간: 26.85 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0<br/>합계: 100.0 / 100.0

제출 일자

2024년 07월 04일 23:45:25

문제 설명

<p>자연수 <code>x</code>를 <code>y</code>로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.</p>

<ul> <li><code>x</code>에 <code>n</code>을 더합니다</li> <li><code>x</code>에 2를 곱합니다.</li> <li><code>x</code>에 3을 곱합니다.</li> </ul>

<p>자연수 <code>x</code>, <code>y</code>, <code>n</code>이 매개변수로 주어질 때, <code>x</code>를 <code>y</code>로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 <code>x</code>를 <code>y</code>로 만들 수 없다면 -1을 return 해주세요.</p>

<hr>

<h5>제한사항</h5>

<ul> <li>1 ≤ <code>x</code> ≤ <code>y</code> ≤ 1,000,000</li> <li>1 ≤ <code>n</code> < <code>y</code></li> </ul>

<hr>

<h5>입출력 예</h5> <table class="table"> <thead><tr> <th>x</th> <th>y</th> <th>n</th> <th>result</th> </tr> </thead> <tbody><tr> <td>10</td> <td>40</td> <td>5</td> <td>2</td> </tr> <tr> <td>10</td> <td>40</td> <td>30</td> <td>1</td> </tr> <tr> <td>2</td> <td>5</td> <td>4</td> <td>-1</td> </tr> </tbody> </table> <hr>

<h5>입출력 예 설명</h5>

<p>입출력 예 #1<br> <code>x</code>에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.</p>

<p>입출력 예 #2<br> <code>x</code>에 <code>n</code>인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.</p>

<p>입출력 예 #3<br> <code>x</code>를 <code>y</code>로 변환할 수 없기 때문에 -1을 return합니다.</p>

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

풀이

java코드 복사
class Solution {
    
    private static final int MAX = Integer.MAX_VALUE;

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

        int[] dp = new int[y + 1];

        for (int i=x+1; i<y+1; i++) {
            int a= MAX, b= MAX, c= MAX, d;

            if (isDivided(i, 2) && aboveX(x, i/2)) a= dp[i/2];
            if (isDivided(i, 3) && aboveX(x, i/3)) b= dp[i/3];
            if (aboveX(x, i-n)) c= dp[i-n];

            //숫자 i를 만들기 위한 최소 방법을 찾음
            d= Math.min(a, b);
            d= Math.min(d, c);

            //만들 수 있으면 d+1 저장
            //만들 수 없다면 MAX 저장
            dp[i]= (d < MAX) ? d + 1 : MAX;
        }

        //y를 만들 수 없다면 -1 반환
        answer= (dp[y] < MAX) ? dp[y] : -1;

        return answer;
        
    }

    //x 보다 작은 위치의 값을 비교하지 않게 함
    private static boolean aboveX(int x, int num) {
        return (num >= x);
    }

    //(i/2), (i/3)의 연산 결과가 자연수인지 확인
    private static boolean isDivided(int num, int divide) {
        return (num/divide>0 && num%divide==0);
    }

}