코테/Greedy
[C/C++] 나동빈 곱하기 혹은 더하기, Greedy
상똥
2023. 2. 6. 16:24
문제
각 자리가 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보다 작을동안 반복한다.