프로그래머스 LV.2 숫자 변환하기

https://github.com/kwon1232/CodingTest/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/154538.%E2%80%85%EC%88%AB%EC%9E%90%E2%80%85%EB%B3%80%ED%99%98%ED%95%98%EA%B8%B0

CodingTest/프로그래머스/2/154538. 숫자 변환하기 at main · kwon1232/CodingTest

 

 

 

 

 

#include <string>
#include <vector>

using namespace std;

int solution(int x, int y, int n) {
    
    vector<int> dp(y + 1, -1);
    dp[x] = 0;

   
    for (int i = x; i <= y; ++i) {
        if (dp[i] == -1) 
            continue;              
        int nextCnt = dp[i] + 1;

        if (i + n <= y) {
            if (dp[i + n] == -1 || dp[i + n] > nextCnt)
                dp[i + n] = nextCnt;
        }

        if ((long long)i * 2 <= y) {
            if (dp[i * 2] == -1 || dp[i * 2] > nextCnt)
                dp[i * 2] = nextCnt;
        }

        if ((long long)i * 3 <= y) {
            if (dp[i * 3] == -1 || dp[i * 3] > nextCnt)
                dp[i * 3] = nextCnt;
        }
    }

    return dp[y];
}

 

 

 

Work Flow

1. 초기화
   • dp 크기를 y+1로 잡고, 모두 -1로 설정
   • 출발점 dp[x] = 0
2. 순방향 순회 (i = x → y)
   • dp[i] == -1 이면 “도달 불가” 상태이므로 건너뛰고
   • 유효한 i에 대해서만 다음 세 연산을 적용
3. 세 연산 적용
   • i + n → dp[i+n] = dp[i] + 1 (더 작으면 갱신)
   • i * 2, i * 3 도 마찬가지로 dp[...] 갱신
4. 결과 반환
   • 루프 종료 후 dp[y]를 리턴
   • dp[y] == -1 이면 -1 (불가), 아니면 최소 연산 횟수

 

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

프로그래머스