BOJ - 1541 잃어버린 괄호

문제 링크 : https://www.acmicpc.net/problem/1541

문제 유형 : 그리디 알고리즘

문제 티어: 실버2 

문제 풀이

1) 최솟값을 찾아야 하기 때문에 일단 "-" 기준으로 수식을 나눈다. 

2) ( ) - ( ) 기준으로 나왔을 때 무조건 뒷 괄호를 크게 만들어놓고 앞 괄호에서 뒷 괄호를 빼는게 제일 최솟값일 것이다. 

3) 만약 - 기준으로 나눴을 때 +로 묶인 부분이 있으면 더해주어야 한다.

4) 첫 번째 괄호는 그냥 더해주고 두 번째 괄호부터는 다 빼주는게 제일 최솟값일 것이다(이미 -로 구분 지었고 첫 번째는 숫자로 시작 즉, + 이기 때문에 더해줘야 함)

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
// -로 나누어서 값 입력 받음
let groups = input[0].split("-");
let answer = 0; // 최솟값 받을 변수
// 반복문
for(let i=0;i<groups.length;i++){
   let cur = groups[i].split("+").map(Number).reduce((a,b)=>a+b);
   // 첫 번째 값일 때 
   if(i==0){
       answer+=cur;
       }else {
          answer -= cur; // 두 번째 값 이상일 때
          }
  }
  console.log(answer);

 

또한 이번 문제에서 부터 GPTs를 제작해 백준 코딩테스트 문제 분석을 통해 공부하고 있는데 GPTs로 만든 문제 풀이도 함께 첨부하고자 한다. 직접 공부할 때 사용하려고 제작한 GPTs이니 비슷한 상황에 있는 분들도 함께 공부했으면 좋겠다는 마음으로 공유한다. 
GPTs 링크 : 

백준 코딩테스트 문제 풀이 : https://chatgpt.com/g/g-uWf5rBEwE-baegjun-algorijeum-bbusyeobbusyeo

ChatGPT - 백준 알고리즘 뿌셔뿌셔

 

문제 접근 방법

1. 입력 분석: 수식은 '+'와 '-' 연산자로 이루어져 있습니다. 이 수식에서 괄호를 배치하여 결과를 최소화해야 합니다.
2. 그리디 알고리즘:
   • '-' 연산자를 기준으로 수식을 나눕니다.
   • '-'를 기준으로 나누어진 각 부분을 괄호로 묶으면, 첫 번째 부분을 제외한 나머지 부분은 모두 빼는 것이 결과를 최소화하는 방법입니다.
   • 예를 들어, 수식이 "55-50+40"이라면 이를 "(55)-(50+40)"으로 만드는 것이 결과를 최소화할 수 있습니다.

단계별 문제 풀이

1. 수식 분해: '-'를 기준으로 수식을 분해합니다. 이때, 첫 번째 부분은 더하고 나머지 부분은 모두 빼는 방식으로 처리합니다.
2. 부분 합 계산: 분해된 각 부분에서 '+' 연산자를 기준으로 부분 합을 계산합니다.
3. 최종 계산: 첫 번째 부분의 합에서 나머지 부분의 합을 뺍니다.

단계별 상세 설명

1. 수식 분해:
   • '-'를 기준으로 문자열을 분할하여 배열로 만듭니다.
   • 예를 들어, "55-50+40"은 ["55", "50+40"]으로 분해됩니다.
2. 부분 합 계산:
   • 각 분해된 부분에서 '+' 연산자를 기준으로 다시 분할하여 숫자들의 합을 계산합니다.
   • 예를 들어, "50+40"은 50과 40을 더하여 90이 됩니다.
3. 최종 계산:
   • 첫 번째 부분의 합에서 나머지 부분의 합을 차례대로 뺍니다.
   • 예를 들어, "55-(50+40)"은 55에서 90을 빼서 -35가 됩니다.

문제 해결 전략

• 수식을 '-'로 나누고, 각 부분을 '+'로 다시 나누어 계산합니다.
• 첫 번째 부분은 무조건 더하고, 이후의 모든 부분은 뺍니다.