https://www.acmicpc.net/problem/3015
๋ฌธ์
์ค์์์ค์ ์ฌ๊ฒฐํฉ ๊ณต์ฐ์ N๋ช ์ด ํ ์ค๋ก ์์ ๊ธฐ๋ค๋ฆฌ๊ณ ์๋ค.
์ด ์ญ์ฌ์ ์ธ ์๊ฐ์ ๋ง์ดํ๊ธฐ ์ํด ์ค์์์ ๊ธฐ๋ค๋ฆฌ๊ณ ์๋ ๋ฐฑ์ค์ด๋ ๊ฐ์๊ธฐ ์๊ธฐ๊ฐ ๋ณผ ์ ์๋ ์ฌ๋์ ์๊ฐ ๊ถ๊ธํด ์ก๋ค.
๋ ์ฌ๋ A์ B๊ฐ ์๋ก ๋ณผ ์ ์์ผ๋ ค๋ฉด, ๋ ์ฌ๋ ์ฌ์ด์ A ๋๋ B๋ณด๋ค ํค๊ฐ ํฐ ์ฌ๋์ด ์์ด์ผ ํ๋ค.
์ค์ ์์๋ ์ฌ๋์ ํค๊ฐ ์ฃผ์ด์ก์ ๋, ์๋ก ๋ณผ ์ ์๋ ์์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ค์์ ๊ธฐ๋ค๋ฆฌ๊ณ ์๋ ์ฌ๋์ ์ N์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 500,000)
๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๊ฐ ์ฌ๋์ ํค๊ฐ ๋๋ ธ๋ฏธํฐ ๋จ์๋ก ์ฃผ์ด์ง๋ค. ๋ชจ๋ ์ฌ๋์ ํค๋ 231 ๋๋ ธ๋ฏธํฐ ๋ณด๋ค ์๋ค.
์ฌ๋๋ค์ด ์ ์๋ ์์๋๋ก ์ ๋ ฅ์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์๋ก ๋ณผ ์ ์๋ ์์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
ํ์ด1 - ์คํจ
(๋ฐ๋ก ์๋ ค์ค.. ์ ๋ฐ..)
์ฒ์์ ์๋ํ ๋์ ํ์ด..
input๋ค์ ๋ฒกํฐ๋ก ๋ฐ๊ณ ์ด์ค for๋ฌธ์ ์ด์ฉํด์ ํ์๋๋ฐ
์๊พธ 9% ์์ ํ๋ ธ๋ค๊ณ ๋์ด ใ ใ ใ
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector <int> input;
stack <int> s;
long long ans = 0;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// ์
๋ ฅ
int n;
cin >> n;
for(int i=0; i<n; i++){
int tmp;
cin >> tmp;
input.push_back(tmp);
}
// ๊ณ์ฐ
for(int i=0; i<n; i++){
s.push(0);
for(int j=i+1; j<n; j++){
if(s.top() > input[j]){
break;
}
ans++;
if(input[i] < input[j]){
break;
}
s.push(input[j]);
}
while(!s.empty()) s.pop();
}
// ์ถ๋ ฅ
cout << ans;
return 0;
}
์๋ฌดํผ ์๋ฌด๋ฆฌ ์ด์ฌํ ๊ฒ์ํ์ ๋ค์ ธ๋ด๋ ์๋ผ์..
๋ค๋ฅธ ํ์ด๋ก ๊ฐ๋ค
ํ์ด 2
์ ๋ ฅ์ ๋ฐ๋ ๋์์ ์คํ์ ๋ฃ์ผ๋ฉด์ ๊ณ์ฐํ๋ ์ค์๊ฐ ํ์ด
์๊ฐ๋ณต์ก๋ ๋ฉด์์๋ ์ด๊ฒ ๋ ๋ซ๋ค
๋ค๋ง ํ์ด๊ฐ ์กฐ๊ธ. ๋ง์ด. ๋ณต์กํ ๋ฟ..
์ฐ์ ๋ชจ๋ ์ ๋ค์ ํค๊ฐ ๋ค ๋ค๋ฅด๋ค๊ณ ๊ฐ์ ํด์ ๊ฐ๋จํ๊ฒ ๋ก์ง์ ๊ตฌ์ฑํ๋ค
ํ ์คํธ ์ผ์ด์ค๋ ์์ ๋ฅผ ์ด์ง ๋ณํํด์ "6 2 4 1 2 5 1" ์ ๋ฃ์ด ๋ต 7์ด ๋์ค๋ฉด ๋จ
// Authored by : seondal
// Co-authored by : -
//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
using namespace std;
stack<int> s;
long long ans;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
while(n--){
int h;
cin >> h;
// (2)
while(!s.empty() && s.top().first < h){
s.pop();
ans++;
}
// (1)
if(!s.empty()) ans++;
s.push(h);
}
cout << ans;
return 0;
}
/*
*/
๋ก์ง์ ์ค๋ช ํด๋ณด๊ฒ ๋ค
์ฐจ๋ก๋๋ก ๊ฐ์ ์ ๋ ฅ๋ฐ์์ ์คํ์ ๋ฃ์ผ๋ฉฐ ์์ ๋ง๋๋๋ฐ,
์ ๋ ฅ๊ฐ์ด ์์ ์๋ ๊ฐ๊ณผ ์ ์ดํ๋ฉด ํ๋์ ์์ด ์์ฑ๋๋๊ฑฐ๋ผ๊ณ ์๊ฐํ๋ฉด ํธํ๋ค
(ex. top=2 ์ผ๋ 4๋ฅผ ๋ฃ์ผ๋ฉด 2์4 ํ์์ด ๋ง๋ค์ด์ง)
๊ทธ๋ฆฌ๊ณ ํ์์ด ์์ฑ๋ ๋๋ง๋ค ans++;
(1)
๊ทธ๋์ ๋น์ด์์ง ์์ ์คํ์ ๊ฐ์ ๋ฃ์๋๋ง๋ค ans++
์คํ์ด ๋น์ด์๋ค๋ฉด ๋ง๋๋ ์ ๊ฐ ์์ผ๋ฏ๋ก ์์ด ์๋ง๋ค์ด์ก์ผ๋๊น ans ์ฆ๊ฐ์ํค์ง ์๊ณ ๊ทธ๋ฅ push
(2)
์ด๋ ๋ฃ์ผ๋ ค๋ ๊ฐ๋ณด๋ค ๊ผญ๋๊ธฐ ๊ฐ์ด ๋ ์๋ค๋ฉด ์ง๊ธ ๋ฃ์ผ๋ ค๋ ์ ๋ ๊ผญ๋๊ธฐ ๊ฐ ๋ฐ์ ์๋ ์ ๋ ๋ณผ ์ ์์๊ฑฐ๋ค
๋ฐ๋ผ์ ์์ ๋ณด๋ค ์์ ๊ผญ๋๊ธฐ๊ฐ๋ค์ while๋ก ๊ณ์ ๊บผ๋ผ (pop)๊ฑด๋ฐ,
์ด๋ ๊บผ๋ด์ง๋ ์ ๋ค๋ ๋ค ์ง๊ธ ๋ฃ์ผ๋ ค๋ ์ ์ ์์ด ๋ง๋ค์ด์ง๊ธฐ ๋๋ฌธ์ ans++
์ํ์ผ๋ ๋ค์๋จ๊ณ๋ก ๋์ด๊ฐ๋ณด์
ํค๊ฐ ๊ฐ์ ์ ๋ค์ด ์๋๊ฒฝ์ฐ, ๊ทธ ์ ๋ค์ ํ๋๋ก ์ทจ๊ธํ๋ค. (์ค๋ณต์ ์ธ์ ํ์ง ์์)
๊ทผ๋ฐ ๊ณ์ฐ์ ํด์ผํ๊ธฐ ๋๋ฌธ์ ans ์นด์ดํธ๋ฅผ ์ฐ์์ผ๋ก ์ค๋ณต๋ ์ ๋ค ์ ๋งํผ ๋ํด์ฃผ๋ ๋ฐฉ์์ผ๋ก ์งํํ๋ค
์ฐ์์ผ๋ก ์ค๋ณต๋ ์ ๋ค ์๋ฅผ ํํํ๊ธฐ ์ํด pair<int, int> ๋ฅผ ์ด์ฉํ์ฌ ์ฒซ๋ฒ์งธ๋ ํค๋ฅผ, ๋๋ฒ์งธ๋ ์ฐ์ ์ค๋ณต ์๋ฅผ ํํํ๊ธฐ๋ก ํ๋ค.
(1) pop์ ํ ๋ ans๋ฅผ ํ๋์ฉ ์ฆ๊ฐ์ํค์ง ์๊ณ ๊ผญ๋๊ธฐ์ ์ฐ์ ์ค๋ณต ์ ๋งํผ ์ฆ๊ฐ์ํจ๋ค.
(2) ๋ฃ์ผ๋ ค๋ ์ ์ ๊ผญ๋๊ธฐ ์ ํค๊ฐ ๊ฐ๋ค๋ฉด,
(3) ๋ค์ด๊ฐ๋ ์ ๋ ์์ ๊ณผ ๊ฐ์ ํค์ ์ ์์ ์์ ์ด๋ฃจ๊ณ ์์ผ๋ฏ๋ก ๊ผญ๋๊ธฐ ์ ์ second ๊ฐ์ ++ ํด์ค๋ค. (์ฐ์ ์ค๋ณต ์ ์ฆ๊ฐ)
(4) ๊ทธ๋ฆฌ๊ณ ๊ทธ ์ ์ ์์ ๊ณผ ๊ฐ์ ํค์ธ ์ ๋ค๊ณผ๋ ์์ ์ด๋ฃจ๋ฏ๋ก ans ๋ฅผ ์ฐ์ ์ค๋ณต ์๋งํผ ์ฆ๊ฐ
(5) ๊ทผ๋ฐ ๋ฃ์ผ๋ฉด์ ๊ฐ์ํค๋ค ๋ค์ ํฐ ํค ํ๋๊ฐ ์๋ค๋ฉด ๊ฑ๋ ์์ ์ด๋ฃจ๋ฏ๋ก ans++;
// Authored by : seondal
// Co-authored by : -
//#include <bits/stdc++.h>
#include <iostream>
#include <stack>
using namespace std;
stack<pair<int, int>> s;
long long ans;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
while(n--){
int h;
cin >> h;
// (1)
while(!s.empty() && s.top().first < h){
ans += s.top().second;
s.pop();
}
// (2)
if(!s.empty() && s.top().first == h) {
ans += s.top().second; //(4)
s.top().second++; //(3)
// (5)
if(s.size() > 1) ans++;
continue;
}
if(!s.empty()) ans++;
s.push({h,1});
}
cout << ans;
return 0;
}
/*
*/
๋!
๋ด์ธ์ ์ฒซ Gold1!!
์๊ณ ํ๋ค!!!
'๐ Baaaaaarking > 0x05๊ฐ - ์คํ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ G4][C++] ๋ฐฑ์ค 17298๋ฒ: ์คํฐ์ (1) | 2022.02.13 |
---|---|
[BOJ G5][C++] ๋ฐฑ์ค 6198๋ฒ: ์ฅ์ ์ ์ ๊พธ๋ฏธ๊ธฐ (0) | 2022.02.13 |
[BOJ G5][C++] ๋ฐฑ์ค 2493๋ฒ: ํ (0) | 2022.02.12 |
[BOJ][C++] 1874๋ฒ : ์คํ ์์ด (0) | 2022.01.08 |
[BOJ][C++] ๋ฐฑ์ค 10773๋ฒ : ์ ๋ก (0) | 2022.01.06 |