[백준] js 1541 - 그리디 알고리즘

그리디 알고리즘..

솔직히 막 이름은 있어보이는데

결론적으로는 그냥 가장 최적의 방식을 쓰는 알고리즘이라는 말 같다

 

이 문제는 괄호를 쓰면 먼저 계산되는 순서를 통해서

가장 최소값을 만드는 것이 문제다.

 

덧셈끼리 있을땐 괄호가 사실 필요없고..

마이너스끼리 있을때..도 괄호가 크게 필요없고

덧셈과 마이너스가 같이 있을때 이제 덧셈끼리는 다 더하고

빼버리는게 가장 크게 최소값을 만드는 방법이라는 것을 찾으면 꽤 풀기 쉽다(근데 난 어렵다 여전히!!!!!!!!!!!!)

그니까 

 

55 - 40 + 54 라는 문장에서

55 / 40+54 로 -를 기준으로 묶고 (괄호를 추가한다는 뜻)

40+54를 먼저 진행해준뒤

모든 계산을 -로 진행해주면 최소 값이 나온다

// readline 모듈보다는 fs를 이용해 파일 전체를 읽어 들여 처리하기
const fs = require('fs')

const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "test.txt")
  .toString()
  .trim()
  .split("\n");

// data[0].split('-').map(Number);
function solution(data) {
    // -를 기준으로 가장 크게 묶어야 가장 최소로 만들 수 있음
    let dataOrg = data[0].split('-');
    let dat = 0;
    let sum = 0;

    for(let i = 0 ; i < dataOrg.length ; i++){
        dat = dataOrg[i].split("+").map(Number).reduce((acc,curr) => acc + curr , 0);
        if(i==0){
            sum += dat;
            continue;
        }
        sum -= dat;
    }
    
    console.log(sum);
    return;
}

solution(input);