[C/C++] 나동빈 곱하기 혹은 더하기, Greedy

문제

각 자리가 0~9로 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 삽입하여 만들 수 있는 가장 큰 수를 도출하라. 단, 덧셈보다 곱셈이 우선시되는 연산의 기본 법칙은 무시하며 왼쪽 연산부터 차례로 계산한다고 가정한다. 예를 들어 02984라는 문자열이 주어지면 가장 큰 수는(((0+2)x9)x8)x4=576이다.

코드

#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

int main() {
	string S;
	cin >> S;
	int temp1, temp2, index = 0;

	temp1 = stoi(S.substr(index, 1));
	while (index < S.length() - 1) {
		temp2 = stoi(S.substr(index + 1, 1));
		if ((temp1 <= 1) || (temp2 <= 1)) {
			temp1 += temp2;
		}
		else
			temp1 *= temp2;
		index++;
	}
	cout << temp1;
}

풀이

1. 문자열의 각 문자를 가리킬 변수 index를 0으로 초기화한다.

2. S의 index번째 문자를 int 타입의 temp1에 저장한다.

3. S의  index번째 또는 index+1번째 문자가 0이면 두 수를 더해 temp1에 저장하고 index를 1씩 증가시킨다.

4. S의  index번째 또는 index+1번째 문자가 0이 아니라면 두 수를 곱해 temp1에 저장하고 index를 1씩 증가시킨다.

5. 3~4번 과정을 index가 S의 길이-1보다 작을동안 반복한다.