[ 그리디 ] 02 곱하기 혹은 더하기

난이도 : 하 풀이시간 : 30분 시간제한 : 1초 기출 : facebook 인터뷰

[ 그리디 ] 02 곱하기 혹은 더하기

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '*' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 *를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.
예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰수는 ((((0+2)*9)*8)*4) = 576 입니다.

 

:: 입력 조건

 

첫째 줄에 여러 개의 숫자로 구성도니 하나의 문자열 S가 주어집니다. (1<=S의 길이<=20)

 

:: 출력 조건

 

첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.

 

---

  내   코드  

 

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main(void) {
	string s;

	cin >> s;

	vector<int> nums;
	int total = 0;

	for (int i = 0; i < s.length(); i++) {
		int k = s[i] - '0';
		nums.push_back(k);
	}

	int a = nums[0];
	int b = nums[1];

	a + b > a * b ? total = a + b: total = a * b;
	// 첫 항과 두번째 항에 대해서만 먼저 연산을 수행해서 값을 total에 저장

	for (int i = 2; i < s.length(); i++) {
		int c = nums[i];
		c+  total > c * total ? total = c + total : total = c * total;
	}

	cout << total;
}

0이나 1인지 체크해서 하려다가 그냥 연산을 수행해보고 결과를 비교하는 방식으로 풀었음

근데 답지에는 0이나 1인지 체크하고 아닌 경우에 무조건 곱하기 연산을 수행함

생각해보니까 연산을 다 수행해서 비교하면 불필요한 연산을 많이 하게 됨

---

2021.07.19

 

안 푼 줄 알고 다시 풀었음 ,, 

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
	string s;
	cin >> s;

	vector<int> nums;

	for (int i = 0; i < s.length(); i++) {
		nums.push_back(s[i]-'0');
	}

	int result = nums[0];

	for (int i = 1; i < nums.size(); i++) {
		if (nums[i] == 0 || nums[i] == 1 || result == 0) {
			result += nums[i];
		}
		else result *= nums[i];
	}

	cout << result << "\n";
}

이번에는 0과 1을 체크해서 더하기를 수행한다는 아이디어를 생각해냄

하지만 원래 저장된 값이 1일 경우를 산정하지 못햇음

if (nums[i] <=1 || result <= 1) // 23번째 줄 조건문을 이렇게 수정하는 게 맞음

 

  정답  코드  

 

#include <bits/stdc++.h>

using namespace std;

string str;

int main(void) {
    cin >> str;

    // 첫 번째 문자를 숫자로 변경한 값을 대입
    long long result = str[0] - '0';

    for (int i = 1; i < str.size(); i++) {
        // 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
        int num = str[i] - '0';
        if (num <= 1 || result <= 1) {
            result += num;
        }
        else {
            result *= num;
        }
    }

    cout << result << '\n';
}