[코드트리] 수를 여러번 사용하여 특정 수 만들기

 

 

https://www.codetree.ai/missions/5/problems/create-a-specific-number-using-multiple-numbers?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

뭔가 해결책보다 i와 j의 범위를 구하는 것이 어려웠다. 그래서 최악의 경우인 1000을 넣었다.

그러다보니 생각보다 많은 범위를 탐색하였다.

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int a, b, c;
int main() {
    cin >> a >>  b >> c;

    int minNum = 21e8, answer;
    for(int i=0; i<1000; i++){
        for(int j=0; j<1000; j++){
            int sum = (a * i) + (b * j);
            if(sum > c) continue;
            if(minNum > abs(sum - c)){
                minNum = abs(sum - c);
                answer = sum;
                
            }
        }
    }

    cout << answer;
    return 0;
}

 

해설을 보니 좀 더 효율적인 방법을 택했다.

c/a를 해서 그 횟수만큼만 진행하는 것이다. 또한 b의 횟수의 경우 a의 횟수에 맞게 자동적으로 계산되기에 또 for문을 사용할 필요가 없다. 

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int a, b, c;
int main() {
    cin >> a >>  b >> c;

    int answer = 0;
    for(int i=0; i*a<= c; i++){
        int cnt = i * a;

        int numB = (c - cnt) / b;
        cnt += numB * b;
        answer = max(answer, cnt);
    }

    cout << answer;
    return 0;
}