https://www.acmicpc.net/problem/1158
๋ฌธ์
์์ธํธ์ค ๋ฌธ์ ๋ ๋ค์๊ณผ ๊ฐ๋ค.
1๋ฒ๋ถํฐ N๋ฒ๊น์ง N๋ช ์ ์ฌ๋์ด ์์ ์ด๋ฃจ๋ฉด์ ์์์๊ณ , ์์ ์ ์ K(≤ N)๊ฐ ์ฃผ์ด์ง๋ค. ์ด์ ์์๋๋ก K๋ฒ์งธ ์ฌ๋์ ์ ๊ฑฐํ๋ค. ํ ์ฌ๋์ด ์ ๊ฑฐ๋๋ฉด ๋จ์ ์ฌ๋๋ค๋ก ์ด๋ฃจ์ด์ง ์์ ๋ฐ๋ผ ์ด ๊ณผ์ ์ ๊ณ์ํด ๋๊ฐ๋ค. ์ด ๊ณผ์ ์ N๋ช ์ ์ฌ๋์ด ๋ชจ๋ ์ ๊ฑฐ๋ ๋๊น์ง ๊ณ์๋๋ค. ์์์ ์ฌ๋๋ค์ด ์ ๊ฑฐ๋๋ ์์๋ฅผ (N, K)-์์ธํธ์ค ์์ด์ด๋ผ๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด (7, 3)-์์ธํธ์ค ์์ด์ <3, 6, 2, 7, 5, 1, 4>์ด๋ค.
N๊ณผ K๊ฐ ์ฃผ์ด์ง๋ฉด (N, K)-์์ธํธ์ค ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์์๋๋ก ์ฃผ์ด์ง๋ค. (1 ≤ K ≤ N ≤ 5,000)
์ถ๋ ฅ
์์ ์ ๊ฐ์ด ์์ธํธ์ค ์์ด์ ์ถ๋ ฅํ๋ค.
ํ์ด
๊ณ ๊ตฐ๋ถํฌ
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,k;
cin >> n >> k;
//์ฃผ์ด์ง ๋ฒกํฐ ๋ง๋ค๊ธฐ
vector <int> v(n);
for(int i=0; i<n; i++)
v[i] = i+1;
//์ถ๋ ฅํ ๋ต ๋ฒกํฐ
vector <int> ans(n);
//๊ณ์ฐ
for(int i=n, m=0; i>0; i--, m++){
if(i==1){
ans[m] = v[0];
}
else if(i<k){
ans[m] = v[k%i-1];
}
else{
ans[m] = v[k-1];
}
vector <int> nv(i-1);
//nv ๋ฒกํฐ์ ๊ธฐ์กด ๋ฒกํฐ k ๋ค์ ๋ด์ฉ๋ค ํ ๋น
for(int t=0; t<i-1; t++){
int a = k+t;
if(a>i-1)
a = k+t-i;
nv[t] = v[a];
}
//๊ธฐ์กด ๋ฒกํฐ์ new ๋ฒกํฐ ํ ๋น
for(int t=0; t<i-1; t++){
v[t] = nv[t];
}
}
//์ถ๋ ฅ
cout << "<";
for(int i=0; i<n; i++){
cout << ans[i];
if(i != n-1)
cout << ", ";
}
cout << ">";
return 0;
}
์ด ๋ฌธ์ ์ ํฌ์ธํธ
1. ๋ฌธ์ ์๋ ์์ด๋ผ๊ณ ์ฃผ์ด์ก์ง๋ง vector์ ์ด์ฉํด ํ์ดํ๊ธฐ ์ํด ์ผ์๋ก ์๊ฐํ๋ค.
2. ์ด์๋จ์ (์ ์ธ๋) ์ ๋ค์ ๋ค์ ๋ค๋ก ๊ฐ์ ์ฐจ๋ก๋ฅผ ๊ธฐ๋ค๋ฆฐ๋ค.
3. k๋ฒ์งธ (ํน์ nk๋ฒ์งธ) ์ ๋ค์ ์ ์ธ๋๋ค.
#include <iostream>
#include <vector>
using namespace std;
int main() {
//์
๋ ฅ
int n,k;
cin >> n >> k;
//๊ณ์จ
vector <int> v, ans;
for (int i=0; i<n; i++)
v.push_back(i+1);
for (int t=0,m=0; m<n; t++){
if(t%k == k-1){
ans.push_back(v[t]);
m++;
}
else {
v.push_back(v[t]);
}
}
//์ถ๋ ฅ
cout << "<";
for(int i=0; i<n; i++){
if(i == n-1){
cout << ans[i];
}
else{
cout << ans[i] << ", ";
}
}
cout << ">";
return 0;
}
'๐๏ธ ICPC Sinchon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++][BOJ] ๋ฐฑ์ค 21316๋ฒ: ์คํผ์นด (0) | 2021.08.11 |
---|---|
[C++] ๋ฐฑ์ค 1448๋ฒ: ์ผ๊ฐํ ๋ง๋ค๊ธฐ (0) | 2021.07.26 |
[์๊ฐ์ด๊ณผ][C++] ๋ฐฑ์ค 10825๋ฒ : ๊ตญ์์ (0) | 2021.07.23 |
[C/C++] ๋ฐฑ์ค 10804๋ฒ : ์นด๋ ์ญ๋ฐฐ์น (0) | 2021.07.13 |
[C/C++] ๋ฐฑ์ค15552๋ฒ : ๋น ๋ฅธ A+B (0) | 2021.07.13 |