문제 링크입니다: https://www.acmicpc.net/problem/11775
COCI 2015/2016 D번 문제였습니다.
같은 학교 학우님들과 시간을 정해두고 풀 때는 후위연산식을 이용하여 푸는 문제인 것을 알았지만 구현이 상당히 어려워 결국 풀지 못했던 문제였습니다.
Green55님도 결국 쉬운길을 택하셔서 python 3으로 푸셨고 다른 사람들은 어떻게 풀었는지 확인하기 위해 저도 파이썬 코드를 제출해봤습니다.
COCI 문제들 대부분이 번역이 되어있지 않기 때문에 푼 사람이 별로 없었는데 portableangel님의 코드가 예술이였습니다.
portableangel님의 코드에서 제가 좀 더 이해하기 쉽게 변수명을 바꿔봤습니다.
문제가 된다면 바로 삭제하겠습니다!
알고리즘은 아래와 같습니다.
1. 일차방정식 형태를 갖추는 클래스를 정의합니다.
2. 주어진 수식을 중위연산식에서 후위연산식으로 변형시킵니다.
3. 후위연산식을 계산하여 일차방정식 형태로 만듭니다.
4. 0 ~ (P - 1) 사이의 숫자를 모두 탐색하여 조건을 만족하는 숫자를 찾습니다.
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;
long long M, P;
string s;
class equation
{
public:
long long num; //방정식의 상수
long long coef; //x의 계수
char op; //문자
bool oper; //연산자인지 여부
equation()
{
num = coef = 0;
oper = false;
}
equation(char op) :op(op), oper(true)
{
}
equation(long long num1, long long num2)
{
num = num1, coef = num2;
oper = false;
}
equation operator+(equation &temp)
{
return equation((num + temp.num) % P, (coef + temp.coef) % P);
}
equation operator-(equation &temp)
{
return equation((num - temp.num + P) % P, (coef - temp.coef + P) % P);
}
equation operator*(equation &temp)
{
return equation(num * temp.num % P, (num * temp.coef + coef * temp.num) % P);
}
};
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s >> M >> P;
vector<equation> postfix;
stack<equation> st;
long long temp = 0;
for (int i = 0; i < s.size(); i++)
{
//숫자이면
if ('0' <= s[i] && s[i] <= '9')
{
temp *= 10;
temp += s[i] - '0';
temp %= P;
}
//X 입력시
else if (s[i] == 'x')
{
if (!temp)
temp = 1;
postfix.push_back(equation(0, temp));
temp = 0;
}
else
{
//그 전에 숫자였다면
if (i && '0' <= s[i - 1] && s[i - 1] <= '9')
{
postfix.push_back(equation(temp, 0));
temp = 0;
}
if (s[i] == '(')
st.push(equation('('));
else if (s[i] == ')')
{
while (st.top().op != '(')
{
postfix.push_back(st.top());
st.pop();
}
st.pop();
}
else if (s[i] == '*')
st.push(equation('*'));
//+, -는 *보다 우선순위가 떨어진다
else
{
while (!st.empty() && st.top().op == '*')
{
postfix.push_back(st.top());
st.pop();
}
st.push(equation(s[i]));
}
}
}
while (!st.empty())
{
postfix.push_back(st.top());
st.pop();
}
stack<equation> result;
for (int i = 0; i < postfix.size(); i++)
{
if (!postfix[i].oper)
result.push(postfix[i]);
else
{
equation b = result.top();
result.pop();
equation a = result.top();
result.pop();
if (postfix[i].op == '*')
result.push(a * b);
else if (postfix[i].op == '+')
result.push(a + b);
else
result.push(a - b);
}
}
long long num = result.top().num;
long long coef = result.top().coef;
for (long long i = 0; i < P; i++)
{
if ((num + coef * i) % P == M)
{
cout << i << "\n";
break;
}
}
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2798번 블랙잭 (2) | 2018.09.18 |
|---|---|
| 백준 1159번 농구 경기 (0) | 2018.09.18 |
| 백준 2879번 코딩은 예쁘게 (0) | 2018.09.18 |
| 백준 4604번 Steganography (0) | 2018.09.16 |
| 백준 4673번 셀프 넘버 (0) | 2018.09.16 |