7-G 문제의 풀이방식이 궁금해서 질문 드립니다

안녕하세요!

7-G 문제 공부 후에 프로그래머스의

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

숫자 변환하기를 풀어 보았습니다!

딱 문제를 보자마자, 여러번(무제한) 쓸 수 있고

dp 문제라는 생각이 들어 7-G 문제 접근 방식이 생각나서 아래와 같이 처음에 접근 했었습니다!

arr[x] = 0;

for(int i=n; i<= y; i++)

{

arr[i] =min(arr[i],arr[i-n]+1) ;

}

for(int i = 3*x; i<= y; i++)

{

if(i%3 == 0)

arr[i] = min(arr[i],arr[i/3] +1);

}

for(int i=2*x; i<=y; i++)

{

if(i%2 == 0)

arr[i] = min(arr[i],arr[i/2]+1);

}

이렇게 for문을 나누어서 왼쪽부터 오른쪽으로 더해가면서 구하게 하였습니다. 그랬는데 틀렸다는 메세지가 나와서 혹시나 싶어서 for문을 하나 사용하여 모든 조건을 동시에 검사하게 하였더니 즉

arr[x] = 0;

for(int i= x; i<=y; i++)

{

if(i%3 == 0)

arr[i] = min(arr[i], arr[i/3]+1);

if(i%2 == 0)

arr[i] = min(arr[i],arr[i/2]+1);

if(i-n >=0)

arr[i] =min(arr[i],arr[i-n] +1) ;

}

위와 같이 제출 하였더니 이번엔 정답 처리되었습니다!

아무리 생각을 해 보아도 최솟값을 구하는 것이기 때문에, 같이 검사하나 따로따로 검사하나 문제가 없을 것이라고 생각하였는데, 곱하기나 나누기의 경우라서 다른 걸까요 아니면 비슷한 문제이지만, 접근 방식이 아예 다른 걸까요?? 위의 두가지 방식에서 달라지는 반례를 찾아보려고 계속 생각해 봤는데, 제 머리로는 잘 모르겠어서 고민 끝에 질문 드립니다!

감사합니다!

혹시나 몰라 아래에 정답으로 제출된 코드 전부 첨부했습니다!

#include <string>

#include <vector>

#include <bits/stdc++.h>

using namespace std;

int arr[1000002] ={0};

int solution(int x, int y, int n) {

fill(arr,arr+1000002,987654321);

arr[x] = 0;

for(int i= x; i<=y; i++)

{

if(i%3 == 0)

arr[i] = min(arr[i], arr[i/3]+1);

if(i%2 == 0)

arr[i] = min(arr[i],arr[i/2]+1);

if(i-n >=0)

arr[i] =min(arr[i],arr[i-n] +1) ;

}

cout<< arr[y]<<endl;

if(arr[y]== 987654321)

return -1;

else

return arr[y];

}

    for(int i = 0; i < n; i++){
        cin >> temp; 
        for(int j = temp; j <= k; j++){
            a[j] = min(a[j], a[j - temp] + 1);
        }
    }