글 읽기 - 이게 왜 그리디 알고리즘이죠?

ssh9234 2년 전 0

연산자에서 -를 만나기 전에는 전부 덧셈 만나고 나서는 전부 뺄셈 하면 되지 않나요?

import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);

        String s = scan.nextLine();
        int [] num = new int[26];
        char [] yeon = new char[24];

        int numC=0;
        int yeonC=0;
        char c=' ';
        int i=0;
        int temp=0;
        while(i<s.length()){
            c= s.charAt(i);
            if(i==s.length()-1){
                temp = temp*10+c-'0';
                num[numC]=temp;
                numC++;
                break;
            }
            if(c=='0'||c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='6'||c=='7'||c=='8'||c=='9'){
                temp=temp*10+c-'0';
            }else{
                num[numC]=temp;
                yeon[yeonC]=c;
                numC++;
                yeonC++;
                temp = 0;
            }
            i++;
        }
        int plus =0;
        int minus= 0;
        int res=0;

        int porm=0;
        for(i =0;i<yeonC;i++){
            if(yeon[i]=='-'){
                porm=1;
            }
            if(porm==0){
                res+=num[i+1];
            }else if(porm==1){
                res-=num[i+1];
            }
        }
        res+=num[0];


        scan.close();
        System.out.println(res);
        
    }
}

adfsfsf 2년 전 0

아마 원래 의도는 어떤 연산자 뒤에 괄호를 두고 어디 앞에 괄호를 닫는 게 최적인지 구해서 푸는 것이었을 것 같네요. 그런데 이게 적어주신 것 같은 간략화된 방식이 존재하니까 헷갈리신 것 같아요. 다만, 그 방법 자체가 그리디 알고리즘을 통해 나오는 것이라고 보시는 게 맞지 않나 싶네요.

Zeta611 2년 전 0

저는 덧셈이 안 남을 때까지 덧셈 연산을 '그리디'하게 앞에서부터 처리한 후, 뺄셈만 남을 경우 앞에서부터 빼는 방식으로 해결했습니다.

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <vector>

int max_eval(std::vector<int> &operands, std::vector<char> &operators)
{
    auto it{begin(operators)};
    while ((it = find(it, end(operators), '+')) != end(operators)) {
        const auto j{next(begin(operands), distance(begin(operators), it))};
        *j += *(j + 1);
        operands.erase(j + 1);
        operators.erase(it);
    }
    return accumulate(cbegin(operands) + 1, cend(operands), operands[0],
                      std::minus<int>());
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<int> operands;
    std::vector<char> operators;
    operands.reserve(25);
    operators.reserve(24);

    std::string str;
    std::getline(std::cin, str);
    std::istringstream iss{str};

    int n;
    char op;
    iss >> n;
    operands.push_back(n);
    while (!iss.eof()) {
        iss >> op >> n;
        operators.push_back(op);
        operands.push_back(n);
    }

    std::cout << max_eval(operands, operators) << '\n';
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이게 왜 그리디 알고리즘이죠?

ssh9234 2년 전 0

adfsfsf 2년 전 0

Zeta611 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말