https://www.acmicpc.net/problem/21318
๋ฌธ์
ํผ์๋ ธ๋ฅผ ์ฌ๋ํ๋ ์์์ด๋ ๋งค์ผ ์์นจ ํผ์๋ ธ ์ฒด์กฐ๋ฅผ ํ๋ค. ์์์ด๋ N๊ฐ์ ์ ๋ณด๋ฅผ ๊ฐ์ง๊ณ ์์ผ๋ฉฐ, 1๋ฒ๋ถํฐ N๋ฒ๊น์ง์ ๋ฒํธ๋ก ๋ถ๋ฅธ๋ค. ๊ฐ ์ ๋ณด๋ 1 ์ด์ 109 ์ดํ์ ์ ์๋ก ํํ๋๋ ๋์ด๋๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ๋์ด๋๋ฅผ ๋ํ๋ด๋ ์๊ฐ ํด์๋ก ์ด๋ ค์ด ์ ๋ณด์ด๋ค. 1 ≤ x ≤ y ≤ N ์ ๋ง์กฑํ๋ ๋ ์ ์ x, y๋ฅผ ๊ณจ๋ผ x๋ฒ๋ถํฐ y๋ฒ๊น์ง์ ์ ๋ณด๋ฅผ ๋ฒํธ ์์๋๋ก ์ฐ์ฃผํ๋ ๊ฒ์ด ํผ์๋ ธ ์ฒด์กฐ์ด๋ค.
์์์ด๋ ํผ์๋ ธ ์ฒด์กฐ๋ฅผ ํ ๋, ์ง๊ธ ์ฐ์ฃผํ๋ ์ ๋ณด๊ฐ ๋ฐ๋ก ๋ค์์ ์ฐ์ฃผํ ์ ๋ณด๋ณด๋ค ์ด๋ ต๋ค๋ฉด ์ค์๋ฅผ ํ๋ค. ๋ค์ ๋งํ์๋ฉด, i(x ≤ i < y)๋ฒ ์ ๋ณด์ ๋์ด๋๊ฐ i + 1๋ฒ ์ ๋ณด์ ๋์ด๋๋ณด๋ค ๋๋ค๋ฉด ์ค์๋ฅผ ํ๋ค. ํนํ, ๋ง์ง๋ง์ผ๋ก ์ฐ์ฃผํ๋ y๋ฒ ์ ๋ณด์์ ์ ๋ ์ค์ํ์ง ์๋๋ค. ์์์ด๋ ์ค๋๋ ํผ์๋ ธ ์ฒด์กฐ๋ฅผ ํ๊ธฐ ์ํด ๋ ์ ์ x์ y๋ฅผ ๊ณจ๋๊ณ , ๋ฌธ๋ ๊ถ๊ธํ ๊ฒ์ด ์๊ฒผ๋ค. ์ค๋ ํ ํผ์๋ ธ ์ฒด์กฐ์์ ์ค์ํ๋ ๊ณก์ ๋ช ๊ฐ๋ ๋ ๊น?
์ ๋ ฅ
์ฒซ ๋ฒ์งธ ์ค์ ์ ๋ณด์ ๊ฐ์ N(1 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค.
๋ ๋ฒ์งธ ์ค์ 1๋ฒ ์ ๋ณด๋ถํฐ N๋ฒ ์ ๋ณด๊น์ง์ ๋์ด๋๊ฐ ๊ณต๋ฐฑ์ ๊ตฌ๋ถ์ผ๋ก ์ฃผ์ด์ง๋ค.
์ธ ๋ฒ์งธ ์ค์ ์ง๋ฌธ์ ๊ฐ์ Q(1 ≤ Q ≤ 100,000)์ด ์ฃผ์ด์ง๋ค.
๋ค์ Q๊ฐ์ ์ค์ ๊ฐ ์ค๋ง๋ค ๋ ๊ฐ์ ์ ์ x, y(1 ≤ x ≤ y ≤ N)๊ฐ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
x๋ฒ๋ถํฐ y๋ฒ๊น์ง์ ์ ๋ณด๋ฅผ ์์๋๋ก ์ฐ์ฃผํ ๋, ๋ช ๊ฐ์ ์ ๋ณด์์ ์ค์ํ๊ฒ ๋ ์ง 0 ์ด์์ ์ ์ ํ๋๋ก ์ถ๋ ฅํ๋ค. ๊ฐ ์ถ๋ ฅ์ ๊ฐํ์ผ๋ก ๊ตฌ๋ถํ๋ค.
์ค๋ฒ 1 ๋์ ํฉ ๋ฌธ์ ์ ๋๋ค.
๋ ์ฌ๋ฆฌ๊ธฐ ์ฌ์ ์ผ๋ ๋ง์ง๋ง ์ฐ์ฐ์์ ํท๊ฐ๋ฆด ์ ์์ผ๋ ์ฃผ์!
๋์ ํ์ด
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int nlist[100001];
int over[100001]={0};
int q;
int x;
int y;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> nlist[i];
if(i==1) over[i] = 0;
else {
over[i] += over[i-1];
if(nlist[i] < nlist[i-1]) over[i]++;
}
}
cin >> q;
for (int i = 0; i < q;++i){
cin >> x >> y;
cout << over[y] - over[x]<<"\n";
}
}
'๐ ์๊ณ ๋ฆฌ์ฆ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/BOJ] 21610 : ๋ง๋ฒ์ฌ ์์ด์ ๋น๋ฐ๋ผ๊ธฐ (์๋ฎฌ๋ ์ด์ ) (0) | 2023.04.05 |
---|---|
[C++/BOJ] 21608 : ์์ด ์ด๋ฑํ๊ต (์๋ฎฌ๋ ์ด์ ) (0) | 2023.04.05 |
[C++/BOJ] 17179 : ์ผ์ดํฌ ์๋ฅด๊ธฐ (์ด์งํ์) (0) | 2023.03.29 |
[C++/BOJ] 2343 : ๊ธฐํ ๋ ์จ (์ด์งํ์) / ์์ (0) | 2023.03.28 |
[C++/BOJ] 5549 : ํ์ฑ ํ์ฌ (๋์ ํฉ) / ์ฝ์ง ๊ธฐ๋ก (0) | 2023.03.28 |