https://www.acmicpc.net/problem/1021
๋ฌธ์
์ง๋ฏผ์ด๋ N๊ฐ์ ์์๋ฅผ ํฌํจํ๊ณ ์๋ ์๋ฐฉํฅ ์ํ ํ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ์ง๋ฏผ์ด๋ ์ด ํ์์ ๋ช ๊ฐ์ ์์๋ฅผ ๋ฝ์๋ด๋ ค๊ณ ํ๋ค.
์ง๋ฏผ์ด๋ ์ด ํ์์ ๋ค์๊ณผ ๊ฐ์ 3๊ฐ์ง ์ฐ์ฐ์ ์ํํ ์ ์๋ค.
- ์ฒซ ๋ฒ์งธ ์์๋ฅผ ๋ฝ์๋ธ๋ค. ์ด ์ฐ์ฐ์ ์ํํ๋ฉด, ์๋ ํ์ ์์๊ฐ a1, ..., ak์ด์๋ ๊ฒ์ด a2, ..., ak์ ๊ฐ์ด ๋๋ค.
- ์ผ์ชฝ์ผ๋ก ํ ์นธ ์ด๋์ํจ๋ค. ์ด ์ฐ์ฐ์ ์ํํ๋ฉด, a1, ..., ak๊ฐ a2, ..., ak, a1์ด ๋๋ค.
- ์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ์ด๋์ํจ๋ค. ์ด ์ฐ์ฐ์ ์ํํ๋ฉด, a1, ..., ak๊ฐ ak, a1, ..., ak-1์ด ๋๋ค.
ํ์ ์ฒ์์ ํฌํจ๋์ด ์๋ ์ N์ด ์ฃผ์ด์ง๋ค. ๊ทธ๋ฆฌ๊ณ ์ง๋ฏผ์ด๊ฐ ๋ฝ์๋ด๋ ค๊ณ ํ๋ ์์์ ์์น๊ฐ ์ฃผ์ด์ง๋ค. (์ด ์์น๋ ๊ฐ์ฅ ์ฒ์ ํ์์์ ์์น์ด๋ค.) ์ด๋, ๊ทธ ์์๋ฅผ ์ฃผ์ด์ง ์์๋๋ก ๋ฝ์๋ด๋๋ฐ ๋๋ 2๋ฒ, 3๋ฒ ์ฐ์ฐ์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํ์ ํฌ๊ธฐ N๊ณผ ๋ฝ์๋ด๋ ค๊ณ ํ๋ ์์ ๊ฐ์ M์ด ์ฃผ์ด์ง๋ค. N์ 50๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๊ณ , M์ N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค์๋ ์ง๋ฏผ์ด๊ฐ ๋ฝ์๋ด๋ ค๊ณ ํ๋ ์์ ์์น๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค. ์์น๋ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , N๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฌธ์ ์ ์ ๋ต์ ์ถ๋ ฅํ๋ค.
ํ์ด
ํ์ ํ์ ์
๋์ ์๋ ์์์ ๊ฐ์ ๊ฐ์ ๋ค๋ฅธ๋ฐฉํฅ ๋์ pushํ๊ณ
์๋ ์๋ ์์๋ pop ํ๋ ๋ฐฉ์์ผ๋ก ์ฝ๊ฒ ๊ตฌํ ๊ฐ๋ฅํ๋ค.
q.push(q.start());
q.pop();
๋ค๋ง ์ด ๋ฌธ์ ์ ํฌ์ธํธ๋ ๋ฐฉํฅ์ด ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ๋๊ฐ๋ผ๋ ์ ์ด๋ค.
๋ฐ๋ผ์ ์์ชฝ ๋ค์ชฝ ์๊ด์์ด ์์ชฝ์ผ๋ก pop push ์ฐ์ฐ์ด ๊ฐ๋ฅํ ๋ฑ(depue)๋ฅผ ์ด์ฉํด์ผํ๋ค.
// ์ผ์ชฝ ํ์
d.push_front(d.back());
d.pop_back();
// ์ค๋ฅธ์ชฝ ํ์
d.push_back(d.front());
d.pop_front();
์ด์ ๊ฐ ๊ฒฝ์ฐ์ ๋ฐ๋ผ
์ฐ์ฐ์ ์ต์ํ ํ ์ ์๋ ํ์ ๋ฐฉํฅ์ ๊ตฌํ๊ณ
ํด๋น ๋ฐฉํฅ์ผ๋ก ํ์ ๋ง ํ๋ฉด ๋๋ค.
์ด๋ ํ์ ํ์๋ ์๋์ ์๋ฆฌ๋ฅผ ์ ์ ์๋๋ก
์ฐ์ฐ ์์์ ๋ฑ์ ์์น๋ฅผ ๊ฐ์ผ๋ก ๊ฐ์ง๋ ์์๋ค์ ์์์ ๋ง๊ฒ ๋ฃ์ด๋์๋ค
์ด์ for๋ฌธ์ผ๋ก ํ์ด๋ณด๋ฉด์ (์ง๊ธ ๋ณด๋ find์ด์ฉํด์ ์์ ์ธ๋ฑ์ค๋ฅผ ๊ตฌํ๋ฉด ๋ ํธํ์ํ ๋ฐ)
(๋ฑ์ ํ๋ ์คํ๊ณผ ๋ฌ๋ฆฌ ๊ฐ ์์์ iterator๋ฅผ ์ด์ฉํ ์ ๊ทผ์ด ๊ฐ๋ฅํ๋ค ex. d[i])
ํด๋น ๊ฐ์ด ๋๊ณผ ์์์ค ์ด๋์ ๋ ๊ฐ๊น์ด์ง ์นด์ดํธํด์ ์ค๋ฅธ์ชฝ ์ผ์ชฝ ๋ฐฉํฅ์ ์ ํ๋ฉด ๋๋ค
๋จ, ์ด๋ ์ฃผ์ํ ์
์ผ์ชฝ์ ์์๋ถํฐ ์นด์ดํธํ๊ธฐ ๋๋ฌธ์ ์ด๊น๊ฐ์ด 0์ด์ง๋ง
์ค๋ฅธ์ชฝ์ ๋์์๋ถํฐ ์นด์ดํธํ๊ธฐ ๋๋ฌธ์ ์ด๊น๊ฐ์ด 1์ด๋ค
(์์์์ ๋งจ๋์ผ๋ก ๊ฐ๋ ์ฐ์ฐ์ด ํ๋ฒ์ด ์ถ๊ฐ๋์ด์์ด์ผ ํจ)
// Authored by : seondal
// Co-authored by : -
//#include <bits/stdc++.h>
#include <iostream>
#include <deque>
using namespace std;
int ans, n, m;
deque<int> d;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// ์๋ฆฌ์ ํด๋นํ๋ ์์ ๋ฃ์ด๋๊ธฐ
cin >> n >> m;
for(int i=1; i<=n; i++) d.push_back(i);
while(m--){
// ์
๋ ฅ
int e;
cin >> e;
// ๋ ๊ฐ๊น์ด ๋ฐฉํฅ ๊ณ ๋ฅด๊ธฐ
int right=1, left=0;
for(int i=0; true; i++){
if(d[i] == e) break;
left++;
}
for(int i=d.size()-1; true; i--){
if(d[i] == e) break;
right++;
}
// ๋ฐฉํฅ์ ๋ง๊ฒ ๋๋ฆฌ๊ธฐ
if(right < left){
for(int i=0; i<right; i++){
d.push_front(d.back());
d.pop_back();
}
ans += right;
} else {
for(int i=0; i<left; i++){
d.push_back(d.front());
d.pop_front();
}
ans += left;
}
d.pop_front();
}
cout << ans;
return 0;
}
/*
*/
'๐ Baaaaaarking > 0x07๊ฐ - ๋ฑ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ P5][C++] 11003๋ฒ: ์ต์๊ฐ ์ฐพ๊ธฐ (0) | 2022.02.25 |
---|---|
[BOJ G5][C++] ๋ฐฑ์ค 5430๋ฒ: AC (0) | 2022.02.23 |