백준: Class 4 - 17144, 1918, 2263
</br>
클래스 4가 거의 끝나 간다
</br>
17144: 미세먼지 안녕!
https://www.acmicpc.net/problem/17144
void func(){
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
int t = 0;
if( mmap[i][j] != -1 && mmap[i][j] != 0 ){
for(int k = 0; k < 4; k++){
int nx = i + dx[k];
int ny = j + dy[k];
if( nx < 0 || r <= nx || ny < 0 || c <= ny || mmap[nx][ny] == -1 ) continue;
visited[nx][ny] += mmap[i][j]/5;
t++;
}
}
mmap[i][j] -= (mmap[i][j]/5) * t;
}
}
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
mmap[i][j] += visited[i][j];
visited[i][j] = 0;
}
}
int x = u;
int y = 2;
int prev = mmap[x][1];
mmap[x][1] = 0;
while( y < c-1 ){
int t = mmap[x][y];
mmap[x][y] = prev;
prev = t;
y++;
}
while( x > 0 ){
int t = mmap[x][y];
mmap[x][y] = prev;
prev = t;
x--;
}
while( y > 0 ){
int t = mmap[x][y];
mmap[x][y] = prev;
prev = t;
y--;
}
while( x < u ){
int t = mmap[x][y];
mmap[x][y] = prev;
prev = t;
x++;
}
x = d;
y = 2;
prev = mmap[x][1];
mmap[x][1] = 0;
while( y < c-1 ){
int t = mmap[x][y];
mmap[x][y] = prev;
prev = t;
y++;
}
while( x < r-1 ){
int t = mmap[x][y];
mmap[x][y] = prev;
prev = t;
x++;
}
while( y > 0 ){
int t = mmap[x][y];
mmap[x][y] = prev;
prev = t;
y--;
}
while( x > d ){
int t = mmap[x][y];
mmap[x][y] = prev;
prev = t;
x--;
}
}
// in main()
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
cin >> mmap[i][j];
if( mmap[i][j] == -1 ){
if( u ) d = i;
else u = i;
}
visited[i][j] = 0;
}
}
for(int i = 0; i < t; i++){
func();
}
int ans = 0;
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
if( mmap[i][j] != -1 ) ans += mmap[i][j];
}
}
cout << ans << endl;
}
나는 시뮬레이션 문제를 은근 좋아하는 것 같다 재밌네
말 그대로 구현해 주면 됨
- 미세먼지 확산: visited[][]에 확산된 미세먼지들을 기록하고, 확산된 만큼 해당 미세먼지를 빼준 뒤 마지막에 원래 맵에 더해 줌.
- 공기청정기 작동: while문으로 각 반시계, 시계 방향으로 미세먼지를 밀어 줌, 마지막 공기청정기에 가면 미세먼지가 없어지므로 따로 처리 안 해 줌
ex) 백준 예제 4
7 8 4
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
-------------
0 0 0 0 0 0 1 8
0 0 1 0 3 0 5 6
-1 2 1 1 0 4 6 5
-1 5 2 0 0 2 12 0
0 1 1 0 5 10 13 8
0 1 9 4 3 5 12 0
0 8 17 8 3 4 8 4
0 0 0 0 0 1 8 6
0 0 1 0 3 0 5 5
-1 0 2 1 1 0 4 6
-1 0 5 2 0 0 2 12
0 1 1 0 5 10 13 0
0 1 9 4 3 5 12 8
8 17 8 3 4 8 4 0
-------------
-------------
0 0 0 0 0 2 7 6
0 0 1 0 3 1 3 5
-1 0 3 1 1 0 6 6
-1 1 1 3 1 2 6 7
0 1 3 1 3 6 9 5
1 5 6 5 5 6 8 7
9 10 9 4 5 6 7 1
0 0 0 0 2 7 6 5
0 0 1 0 3 1 3 6
-1 0 0 3 1 1 0 6
-1 0 1 1 3 1 2 6
1 1 3 1 3 6 9 7
9 5 6 5 5 6 8 5
10 9 4 5 6 7 1 7
-------------
-------------
0 0 0 0 3 5 5 5
0 0 1 0 3 2 5 5
-1 0 0 3 1 1 1 5
-1 0 1 1 3 2 4 5
2 2 4 2 5 4 8 7
9 4 4 4 4 6 7 5
8 9 7 4 6 6 4 6
0 0 0 3 5 5 5 5
0 0 1 0 3 2 5 5
-1 0 0 0 3 1 1 1
-1 0 0 1 1 3 2 4
9 2 4 2 5 4 8 5
8 4 4 4 4 6 7 7
9 7 4 6 6 4 6 5
-------------
-------------
0 0 0 4 3 4 5 5
0 0 1 0 4 4 3 4
-1 0 0 0 3 1 2 2
-1 0 0 1 2 3 3 5
8 3 4 3 1 7 6 4
7 6 4 5 7 3 7 7
9 5 6 4 4 7 5 5
0 0 4 3 4 5 5 4
0 0 1 0 4 4 3 2
-1 0 0 0 0 3 1 2
-1 0 0 0 1 2 3 3
7 3 4 3 1 7 6 5
9 6 4 5 7 3 7 4
5 6 4 4 7 5 5 7
-------------
178
</br>
1918: 후위 표기식
https://www.acmicpc.net/problem/1918
mp['*'] = 2;
mp['/'] = 2;
mp['+'] = 1;
mp['-'] = 1;
for(int i = 0; i < s.size(); i++){
if( isalpha(s[i]) ) ans.push_back(s[i]);
else if( s[i] == '(' ) st.push(s[i]);
else if( s[i] == ')' ){
while( st.top() != '(' ){
ans.push_back(st.top());
st.pop();
}
st.pop();
}
else{
while( st.size() && mp[st.top()] >= mp[s[i]] && st.top() != '(' ){
ans.push_back(st.top());
st.pop();
}
st.push(s[i]);
}
}
while( st.size() ){
ans.push_back(st.top());
st.pop();
}
for(int i = 0; i < ans.size(); i++){
cout << ans[i];
}
cout << endl;
후위 표기식이란 걸 처음 봐서 좀 까다로웠다
연산자 우선순위에 따라 스택을 pop한다.
괄호가 나오면 그 안은 먼저 처리해 줘야 하므로 스택에 넣고 오른쪽 괄호가 나오면 스택에 있는 애들을 pop한다.
ex) a + b * c + d / k * (a - b)
> a + bc*
> abc*+
ans: a
st : +
ans: ab
st : + *
*보다 우선순위가 낮은 게 나올 때까지 스택을 pop(현재 해당 없음)
ans: abc
st : +* +
+보다 우선순위가 낮은 게 나올 때까지 스택을 pop
ans: abc*+
st : +
ans: abc*+d
st : +/
ans: abc*+dk
st : +/ *
*보다 우선순위가 낮은 게 나올 때까지 스택을 pop
ans: abc*+dk/
st : +*
ans: abc*+dk/a
st : +*(
ans: abc*+dk/a
st : +*( -
-보다 우선순위가 낮은 게 나올 때까지 스택을 pop(현재 해당 없음)
ans: abc*+dk/ab
st : +*(- )
(가 나올 때까지 스택을 pop
ans: abc*+dk/ab-
st : +*
ans: abc*+dk/ab-*+
st :
남은 스택을 pop
신기하네
</br>
2263: 트리의 순회
https://www.acmicpc.net/problem/2263
void func(int b, int e, int ind){
if( ind == -1 ) return;
int root = -1;
for(int i = b; i < e; i++){
if( in[i] == post[ind] ){
root = i;
break;
}
}
cout << in[root] << ' ';
if( root != b ) func(b, root, ind-e+root);
if( root != e-1 ) func(root+1, e, ind-1);
}
안 그래도 저번에 5639: 이진 검색 트리(https://cyj893.github.io/algorithm/Algorithm16_8/)를 풀 때 두 오더로 다른 오더 만들기를 정리해볼까 했는데 문제가 또 나와 줬네
이 문제는 중위와 후위로 전위를 만든다.
post의 경우 마지막이 루트이므로, 이 루트를 in에서 찾으면 왼쪽과 오른쪽으로 나눌 수 있다
그리고 왼쪽과 오른쪽을 순서대로 탐색하면 된다. pre는 루트를 먼저 들르므로, 루트를 출력한 후 각 자식들을 탐색한다.
ex)
9
5 3 2 4 1 8 7 9 6
5 3 4 2 8 9 7 6 1
// 일케 생긴 트리
1
/ \
2 6
/ \ /
3 4 7
/ / \
5 8 9
왼 루트 오
5 3 2 4 1 8 7 9 6
5 3 4 2 8 9 7 6 1
왼 오 루트
왼 루트 오
5 3 2 4
5 3 4 2
왼 오 루트
왼 루트 오
5 3
5 3
왼 루트
이런 식
</br>
열심히 합시다
</br>
댓글남기기