[C/C++] 1541: 잃어버린 괄호

1542: 잃어버린 괄호 문제

 

이  문제는 -가 언제 나오냐가 중요하다. -가 나올 때 그 다음 -가 나올때 까지 합을 빼는 것이 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 것이다. 또한 -가 나올 때마다 다음 -가 나올 때까지 합을 빼는 것이 가장 최소이기 때문에 현재에 이익이 문제 전체의 이익이 되는 Greedy 알고리즘의 일종이다.

 

 나는 배열 2개만 써서 구현하였지만 아예 -가 나올 때마다 부분 집합을 만들어서 (slice를 통해) 각 값을 더하거나 빼서 구현할 수도 있을 것 같다!!

 

아래는  소스코드다!! 

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

char arr[52];
int store[3];

int ContinueCalculate(int i,int max)
{
  
  if(arr[i]=='+')
  {
    store[0]+=store[1];
    store[1]=0;
  }
  else //숫자가 들어왔을때
    store[1]=store[1]*10+(arr[i]-48);
  if(i==max ||arr[i+1]=='-') //-이면 store[0]에다가 저장을 해둬야함!
  {
    store[0]+=store[1];
    store[1]=0;
  }
    
  return ++i;
}

int SplitMinus(int i,int max)
{
  int k=store[0]; 
  store[0]=0;
  i++;
  while(arr[i]!='-' && i<=max) //현재에 있는 위치에서 -가 있냐!
    {
      i=ContinueCalculate(i,max);      
    }   
  store[0]=k-store[0];
  store[1]=0;
  return i;
}


int main(void)
  {
    scanf("%s",arr);
    int n=strlen(arr);   
    int i=0;
    while(i<n)
      {
        if(arr[i]=='-')
        {          
          i=SplitMinus(i,n-1);
        }
        else
        {
          i=ContinueCalculate(i,n-1);
          
        }        
      }
    printf("%d",store[0]);
    
  }