백준 7479번 Greatest Product [C++]

https://www.acmicpc.net/problem/7497

 

 

#문제 간단 정리

 

N 이 주어지고 

N 이하의 숫자들에서

 

각 자리수를 곱햇을때 가장 커지는 숫자를 찾는 문제

 

#문제 해결 방법

 

N 이하의 숫자들의 자리수의 곱의 최대라는 말은

4876이면 4 *  8 * 7 * 6  이렇게 곱할 수 있고

4876 이하의 숫자인 3999도

곱해서 3 * 9 * 9 * 9 를 곱해서 최대값을 찾을 수 있다.

 

여기서 쉽게 생각 할 수 있는건 9를 최대한 많이 만든다는건데

 

일단 어떤 자리수를 1내리면 그 뒤에 숫자들은 전부 9로 만들수 있다.

 

때문에 각 자리수를 한번씩 1 내리고 그 뒤에수를 전부 9로 만들어 주면서

 최대값을 찾아주면 된다.

 

#전체 코드

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef long long ll;

int main() {



    string s;
    cin >> s;

    ll startMax = 1;

    for (int i = 0; i < s.length(); i++) {
        
        if (s[i] - '0' != 0) {
            startMax *= s[i] - '0';
        }
    }



    for (int i = 0; i < s.length(); i++) {

        ll tempMax = 1;
        if (s[i] - '0' - 1 != 0) { //1 내려서 0이면 곱하지 않고 넘어감
            tempMax *= s[i] - '0' - 1;
        }

        for (int j = i + 1; j < s.length(); j++) { //이후 자리수들 전부 9로 만들기

            tempMax *= 9;

        }

        for (int t = 0; t < i; t++) { //이전자리수들 곱해주기
            if(s[t] - '0' != 0)
                tempMax *= s[t] - '0';

        }

        startMax = max(tempMax, startMax);
    }

    cout << startMax << '\n';

    return 0;
}