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];

}

안녕하세요 lee님 ㅎㅎ

죄송하지만 강의 내의 문제 말고 프로그래머스 등 다른 문제에 관한 질문은 받지 않고 있습니다.

다만 7 - G를 다시 설명을 드리자면

이 dp는 해당 지점에서의 최적의 최소값을 "쌓는" 코드입니다.

    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);
        }
    }

예를 들어 2원이 있을 때 10원을 만드는 최소의 배열은

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

1 0 2 0 3 ...

이 되는 것은 자명하죠. 여기에다가 3원 4원 등을 추가했을 때 이 배열을 갱신해가면서 결국 n가지 종류의 동전을 기반으로 최적이 최솟값을 만들어준다고 생각하시면 됩니다.

감사합니다.

인프런 커뮤니티 질문&답변