1440 words
7 minutes
[BOJ] 할 수 있다
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 128MB | Big Integer, Implementation |
일단 이 문제는 그냥 구현 문제라서 어려울 것은 딱히 없으나…
범위에 대한 계산 때문에 python을 쓰는게 압도적으로 유리한 것으로 보인다. cpp로 하려면 Big Integer를 구현해야되는 대참사가 일어나고… 시간을 버리게 되고…
빼기 순서를 잘못 적어서 또 날리게 되고… 조심하도록 하자.
조금 빡센 구현 문제는 역시! 귀찮다! 재밌다! 아이디어 문제만큼이나 구현 문제도 생각보다 재미있는 것들이 많으니 한번 다들 풀어보시길~~ 물론 이 문제는 풀지 마세요 별로 좋은거 같지는 않아여… 플딱이가 말하는거라 한귀로 흘리시길…
정답 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <sstream>
#include <iomanip>
#include <string>
using namespace std;
string input;
class BigInteger {
private:
std::vector<int> digits;
bool negative;
void removeLeadingZeros() {
while (digits.size() > 1 && digits.back() == 0) {
digits.pop_back();
}
if (digits.size() == 1 && digits[0] == 0) {
negative = false;
}
}
bool absLess(const BigInteger& other) const {
if (digits.size() != other.digits.size()) {
return digits.size() < other.digits.size();
}
for (int i = digits.size() - 1; i >= 0; i--) {
if (digits[i] != other.digits[i]) {
return digits[i] < other.digits[i];
}
}
return false;
}
BigInteger absAdd(const BigInteger& other) const {
BigInteger result;
result.digits.clear();
int carry = 0;
int maxSize = std::max(digits.size(), other.digits.size());
for (int i = 0; i < maxSize || carry; i++) {
int sum = carry;
if (i < digits.size()) sum += digits[i];
if (i < other.digits.size()) sum += other.digits[i];
result.digits.push_back(sum % 10);
carry = sum / 10;
}
return result;
}
BigInteger absSubtract(const BigInteger& other) const {
BigInteger result;
result.digits.clear();
int borrow = 0;
for (int i = 0; i < digits.size(); i++) {
int diff = digits[i] - borrow;
if (i < other.digits.size()) diff -= other.digits[i];
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
result.digits.push_back(diff);
}
result.removeLeadingZeros();
return result;
}
public:
BigInteger() : negative(false) {
digits.push_back(0);
}
BigInteger(long long num) {
negative = num < 0;
if (negative) num = -num;
if (num == 0) {
digits.push_back(0);
} else {
while (num > 0) {
digits.push_back(num % 10);
num /= 10;
}
}
}
BigInteger(const std::string& str) {
negative = false;
int start = 0;
if (str[0] == '-') {
negative = true;
start = 1;
}
for (int i = str.length() - 1; i >= start; i--) {
digits.push_back(str[i] - '0');
}
removeLeadingZeros();
}
BigInteger operator+(const BigInteger& other) const {
if (negative == other.negative) {
BigInteger result = absAdd(other);
result.negative = negative;
return result;
} else {
if (absLess(other)) {
BigInteger result = other.absSubtract(*this);
result.negative = other.negative;
return result;
} else {
BigInteger result = absSubtract(other);
result.negative = negative;
return result;
}
}
}
BigInteger operator-(const BigInteger& other) const {
if (negative != other.negative) {
BigInteger result = absAdd(other);
result.negative = negative;
return result;
} else {
if (absLess(other)) {
BigInteger result = other.absSubtract(*this);
result.negative = !negative;
return result;
} else {
BigInteger result = absSubtract(other);
result.negative = negative;
return result;
}
}
}
BigInteger operator*(const BigInteger& other) const {
BigInteger result;
result.digits.assign(digits.size() + other.digits.size(), 0);
for (int i = 0; i < digits.size(); i++) {
for (int j = 0; j < other.digits.size(); j++) {
result.digits[i + j] += digits[i] * other.digits[j];
if (result.digits[i + j] >= 10) {
result.digits[i + j + 1] += result.digits[i + j] / 10;
result.digits[i + j] %= 10;
}
}
}
result.negative = negative != other.negative;
result.removeLeadingZeros();
return result;
}
std::pair<BigInteger, BigInteger> divmod(const BigInteger& other) const {
if (other.digits.size() == 1 && other.digits[0] == 0) {
throw std::runtime_error("Division by zero");
}
BigInteger dividend = *this;
BigInteger divisor = other;
dividend.negative = false;
divisor.negative = false;
if (dividend.absLess(divisor)) {
return {BigInteger(0), *this};
}
BigInteger quotient;
quotient.digits.clear();
BigInteger remainder;
remainder.digits.clear();
remainder.digits.push_back(0);
for (int i = dividend.digits.size() - 1; i >= 0; i--) {
remainder = remainder * BigInteger(10) + BigInteger(dividend.digits[i]);
int count = 0;
while (!remainder.absLess(divisor)) {
remainder = remainder - divisor;
count++;
}
quotient.digits.push_back(count);
}
std::reverse(quotient.digits.begin(), quotient.digits.end());
quotient.removeLeadingZeros();
remainder.removeLeadingZeros();
quotient.negative = negative != other.negative;
remainder.negative = negative;
return {quotient, remainder};
}
BigInteger operator/(const BigInteger& other) const {
return divmod(other).first;
}
BigInteger operator%(const BigInteger& other) const {
return divmod(other).second;
}
BigInteger& operator=(const BigInteger& other) {
digits = other.digits;
negative = other.negative;
return *this;
}
bool operator==(const BigInteger& other) const {
return negative == other.negative && digits == other.digits;
}
bool operator!=(const BigInteger& other) const {
return !(*this == other);
}
bool operator<(const BigInteger& other) const {
if (negative != other.negative) {
return negative;
}
if (negative) {
return other.absLess(*this);
} else {
return absLess(other);
}
}
bool operator>(const BigInteger& other) const {
return other < *this;
}
bool operator<=(const BigInteger& other) const {
return *this < other || *this == other;
}
bool operator>=(const BigInteger& other) const {
return *this > other || *this == other;
}
std::string toString() const {
std::string result;
if (negative) result += "-";
for (int i = digits.size() - 1; i >= 0; i--) {
result += (digits[i] + '0');
}
return result;
}
friend std::ostream& operator<<(std::ostream& os, const BigInteger& bi) {
os << bi.toString();
return os;
}
};
using ll = BigInteger;
struct info {
bool isNum;
ll num;
char exp;
};
ll getNumber(int idx){
string result = "";
for(; idx < input.size() && '0' <= input[idx] && input[idx] <= '9'; idx++) result += input[idx];
return ll(result);
}
ll solution(){
return 0LL;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> input;
vector<info> expr;
bool flag = false;
for(int i = 0; i < input.size(); i++){
info currentInfo;
if('0' <= input[i] && input[i] <= '9'){
if(!expr.empty() && expr.back().isNum) {
if(flag) {
cout << "ROCK";
return 0;
}
continue;
}
currentInfo = {true, getNumber(i)};
if(!expr.empty()){
ll into;
if(expr.back().exp == '*'){
expr.pop_back();
into = expr.back().num * currentInfo.num;
expr.pop_back();
currentInfo.num = into;
}else if(expr.back().exp == '/'){
expr.pop_back();
if(currentInfo.num == ll(0)){
cout << "ROCK";
return 0;
}
into = expr.back().num / currentInfo.num;
expr.pop_back();
currentInfo.num = into;
}
}
}
else currentInfo = {false, 0, input[i]};
if ((!expr.empty() && !expr.back().isNum && !currentInfo.isNum &&
expr.back().exp != ')' && currentInfo.exp != '(')
|| (expr.empty() && !currentInfo.isNum && currentInfo.exp != '(')) {
cout << "ROCK";
return 0;
}
flag = false;
expr.push_back(currentInfo);
if(expr.back().isNum) continue;
if(expr.back().exp != ')') continue;
flag = true;
expr.pop_back();
ll currentNumber = expr.back().num;
expr.pop_back();
while(expr.back().exp != '('){
char operation = expr.back().exp; expr.pop_back();
ll otherNumber = expr.back().num; expr.pop_back();
switch (operation) {
case '+':
currentNumber = otherNumber + currentNumber;
break;
case '-':
currentNumber = otherNumber - currentNumber;
default:
break;
}
if(expr.empty()) {
cout << "ROCK";
return 0;
}
}
expr.pop_back();
if(!expr.empty()){
if(expr.back().isNum) {
cout << "ROCK";
return 0;
}
if(expr.back().exp != '(' && (expr.back().exp == '*' || expr.back().exp == '/')){
char operation = expr.back().exp; expr.pop_back();
ll otherNumber = expr.back().num; expr.pop_back();
switch (operation) {
case '+':
currentNumber = otherNumber + currentNumber;
break;
case '-':
currentNumber = otherNumber - currentNumber;
break;
case '*':
currentNumber = currentNumber * otherNumber;
break;
case '/':
if(currentNumber == ll(0)){
cout << "ROCK";
return 0;
}
currentNumber = otherNumber / currentNumber;
break;
default:
break;
}
}
}
expr.push_back({true, currentNumber});
}
if(!expr.back().isNum) {
cout << "ROCK";
return 0;
}
// for(int i = 0; i < expr.size(); i++){
// if(expr[i].isNum)
// cout << expr[i].num << " ";
// else
// cout << expr[i].exp << " ";
// }
// cout << "\n";
ll result = expr.back().num;
expr.pop_back();
while(!expr.empty()){
if(expr.back().isNum) {
cout << "ROCK";
return 0;
}
char operation = expr.back().exp; expr.pop_back();
if(!expr.back().isNum) {
cout << "ROCK";
return 0;
}
ll otherNumber = expr.back().num; expr.pop_back();
if(!expr.empty()){
if(expr.back().isNum){
cout << "ROCK";
return 0;
}
if(expr.back().exp == '-'){
if(operation == '+'){
operation = '+';
result = result - otherNumber;
}else if(operation == '-'){
operation = '-';
result = otherNumber + result;
}
continue;
}
}
switch (operation) {
case '+':
result = otherNumber + result;
break;
case '-':
// cout << otherNumber << " " << result << "\n";
result = otherNumber - result;
break;
default:
break;
}
}
std::cout << std::fixed << std::setprecision(0) << result;
return 0;
}
[BOJ] 할 수 있다
https://compy07.github.io/Blog/posts/boj/1287/