백준: 16362, 16368, 16366
</br>
ICPC 2018 본선 문제 풀어보자
나는 요즘 내 형편없는 실력에 놀라고 있다
</br>
16362: Parentheses
https://www.acmicpc.net/problem/16362
수식을 입력 받아서 아예 틀리면 “error”, 식은 괜찮은데 쓸데없는 괄호가 들어가 있으면 “improper”, 완벽하면 “proper” 출력하기
#include <bits/stdc++.h>
#define Error { cout << "error\n"; return 0; }
using namespace std;
int kind(char c){
if( 'a' <= c && c <= 'z' ) return 1;
if( c == '+' || c == '-' || c == '*' || c == '%' || c == '/' ) return 2;
if( c == '(' ) return 3;
if( c == ')' ) return 4;
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
string s;
getline(cin, s);
vector<int> v;
for(int i = 0; i < s.size(); i++){
if( s[i] != ' ' ){
int k = kind(s[i]);
if( k == -1 ) Error;
v.push_back(k);
}
}
bool isImp = false;
stack<int> st;
for(int i = 0; i < v.size(); i++){
int k = v[i];
int pre = -1;
if( st.size() ) pre = st.top();
if( k == 1 ){
if( pre == 1 ) Error;
st.push(k);
}
else if( k == 2 ){
if( pre != 1 ) Error;
st.push(k);
}
else if( k == 3 ){
if( pre == 1 ) Error;
st.push(k);
}
else if( k == 4 ){
bool isA = true;
int cnt = 0;
int chk = 0;
while( st.size() ){
int a = st.top();
st.pop();
if( isA ){
if( a == 1 ){
cnt++;
isA = false;
}
else Error;
}
else{
if( a == 2 ) isA = true;
else if( a == 3 ){
if( cnt != 2 ) isImp = true;
chk = 1;
break;
}
}
}
if( chk == 0 ) Error;
st.push(1);
}
}
bool isA = true;
int cnt = 0;
while( st.size() ){
int a = st.top();
st.pop();
if( isA ){
if( a == 1 ){
cnt++;
isA = false;
}
else Error;
}
else{
if( a == 2 ) isA = true;
else if( a == 3 ) Error;
}
}
if( cnt != 2 ) isImp = true;
if( isImp ) cout << "improper\n";
else cout << "proper\n";
}
딱 봐도 문자열 파싱해서 스택으로 괄호 검사하고 그러는 건데 은근 구현 귀찮고 오래 걸린다… 이런 게 꼭 가끔 하나씩 나오는 거 같은데
(피연산자, 연산자, 피연산자)가 한 세트가 되고 만약 (피연산자) 꼴이나, (피연산자, 연산자, 피연산자, 연산자, …, 피연산자) 꼴이면 improper하다고 체크해 줘야 한다.
들어오는 종류에 따라 피연산자면 1, 연산자면 2, 괄호 “(“면 3, 괄호 “)”면 4로 구분해서 1 앞에는 1이 못오고, 이런 식으로 error 처리를 한다
그리고 4가 들어오면 스택에 애들을 처리한다. 스택에서 3이 나올 때까지 팝하는데, 여기서 만약 형식에 오류가 있으면 error고, 3이 나오기 전까지 피연산자가 2개가 나오면 proper지면 1개나 3개 이상이면 improper이므로 체크한다.
마지막에 스택에 남은 애도 똑같이 처리하면 끝
</br>
16368: Working Plan
https://www.acmicpc.net/problem/16368
각 사람들이 총 일할 수 있는 시간이 있고, 한 번 일하면 w 동안 일하고 h 동안은 꼭 쉬어야 할 때 스케줄에 맞게 일을 처리할 수 있을까
#include <bits/stdc++.h>
#define P pair<int, int>
using namespace std;
int people[2001];
int days[2001];
int canWork[2001];
vector<int> workedDays[2001];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int m, n, w, h;
cin >> m >> n >> w >> h;
priority_queue<P, vector<P>, less<P>> pq;
for(int i = 1; i <= m; i++){
cin >> people[i];
if( people[i] >= w ) pq.push(make_pair(people[i], i));
}
for(int i = 1; i <= n; i++){
cin >> days[i];
}
stack<P> st;
for(int i = 1; i <= n; i++){
while( days[i] > 0 ){
if( pq.size() == 0 ){
cout << "-1\n";
return 0;
}
int d = pq.top().first;
int ind = pq.top().second;
pq.pop();
if( canWork[ind] > i ){
st.push(make_pair(d, ind));
continue;
}
for(int j = 0; j < w; j++){
if( i+j == n + 1 ) break;
days[i+j]--;
}
canWork[ind] = i + w + h;
workedDays[ind].push_back(i);
if( d-w >= w && canWork[ind] <= n ) pq.push(make_pair(d-w, ind));
}
while( st.size() ){
pq.push(st.top());
st.pop();
}
}
cout << 1 << '\n';
for(int i = 1; i <= m; i++){
for(int a : workedDays[i]){
cout << a << ' ';
}
cout << '\n';
}
}
dp같이 생겼는데… 했는데 문제 힌트 보니까 그냥 그리디에 우선순위 큐다
그래서 생각해 보니 모든 사람이 w와 h가 같으므로 사람 자체에는 의미가 없다. 출력을 위해 저장하는 인덱스 정도
그러니까 대충 그냥 w+h를 한 블럭이라고 생각해서 그 블럭이 제일 많은 사람을 먼저 일에 투입하면 된다.
그런데 그 사람이 현재 일할 수 있을 지 모르므로, canWork[]에 일할 수 있는 날짜를 저장해 놓고 못하면 스택에 넣어둔다
예를 들어서 백준 예제는 4 4 6 2로 3번이 무조건 첫 날에 일하게 된다. 그런데 이거 이러면 나중에 문제 있는 거 아닌가 싶어도, 3번의 스케줄과는 관계없이 그냥 가능한 블럭을 넣는다고 생각하면 전혀 문제 없다.
</br>
16366: Starwars
https://www.acmicpc.net/problem/16366
일단 문제 해석이 겁나 오래 걸림… 영어 공부 해야겠음
그래프가 주어지고, 각 노드들 중 human 기지와 military 기지가 여러 개 있다
각 노드들은 certificate 번호로 이어져 있다. 그래서 어느 human기지 i에서 어느 military 기지 j로 가면 certificate 시퀀스가 만들어 질 거다. 가는 길은 여러가지고, 사이클이 있을 수도 있으므로 유니크하지 않음
외계인이 human 기지가 아닌 곳에서 출발해서, military 기지로 침입하려고 한다. 그런데 human 기지에서 출발해서 military 기지로 도착한 것과 똑같은 certificate 시퀀스가 필요하다. 외계인은 침입할 수 있을까??
human 기지도 여러 개 있고, 외계인이 시작할 수 있는 human 기지가 아닌 곳도 여러 개 있고, military 기지도 여러 개 있다
그리고 굳이 어느 military 기지의 시퀀스인지 구분하지 않는다. human 기지에서 military 기지 A로 도착하는 시퀀스와 human 기지가 아닌 곳에서 military 기지 B로 도착하는 시퀀스가 같아도 외계인이 침입할 수 있다고 본다.
#include <bits/stdc++.h>
#define P pair<int, int>
using namespace std;
vector<P> wormhole[2002];
vector<int> workedDays[2002];
int human[2002];
int military[2002];
int visited[2002][2002];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, w, c, h, m;
cin >> n >> w >> c >> h >> m;
for(int i = 0; i < h; i++){
int a;
cin >> a;
human[a] = 1;
}
for(int i = 0; i < m; i++){
int a;
cin >> a;
military[a] = 1;
}
for(int i = 0; i < w; i++){
int s, c, t;
cin >> s >> c >> t;
wormhole[s].push_back(make_pair(c, t));
}
for(int i = 0; i < n; i++){
if( human[i] ) wormhole[n].push_back(make_pair(0, i));
else wormhole[n+1].push_back(make_pair(0, i));
}
queue<P> q;
q.push(make_pair(n, n+1));
visited[n][n+1] = 1;
while( q.size() ){
int hNow = q.front().first;
int aNow = q.front().second;
q.pop();
if( military[hNow] && military[aNow] ){
cout << "YES\n";
return 0;
}
for(int i = 0; i < wormhole[hNow].size(); i++){
int hC = wormhole[hNow][i].first;
int hNx = wormhole[hNow][i].second;
for(int j = 0; j < wormhole[aNow].size(); j++){
int aC = wormhole[aNow][j].first;
int aNx = wormhole[aNow][j].second;
if( hC == aC && visited[hNx][aNx] == 0 ){
q.push(make_pair(hNx, aNx));
visited[hNx][aNx] = 1;
}
}
}
}
cout << "NO\n";
}
그래서 와… 이거 어떡하지 오토마타로 만들어진 거 가능한 시퀀스 다 저장하고 외계인이 또 가보고 비교해야 할까 막 고민했는데
결국 풀이를 본 결과… 그냥 (human, ailien)을 페어로 시작해서, 둘이 갈 수 있는 곳이 같은 certificate면 거기를 골라서 가보면 된다고 한다!! 생각해 보니 정말 그럼…
더미 human 기지와 더미 ailien 기지를 추가해서 각각 모든 담당 기지에 가는 간선을 추가하고 bfs 한 번만 돌리면 해결이다.
하나라도 찾으면 바로 “YES” 출력하고 bfs를 종료하면 된다.
</br>
이제 토요일 ICPC인데… 괜찮을까
</br>
댓글남기기