BOJ 28036 - Rotate and Shift
내 풀이Permalink
에 속한 인덱스 는 라 할 때, 초부터 이동을 시작하고 한 번 이동할 때 만큼 오른쪽으로 간다.
그리고 그 다음 이동은 초이다.
이러한 성질을 이용해 풀 수 있다.
즉, 초 후의 위치는 이다.
void solve() {
int n, k, t;
cin >> n >> k >> t;
vi rot(k);
fv(rot);
rot.pb(n);
vi ans(n, -1);
for (int i = 0; i < k; i++) {
int l = rot[i], r = rot[i + 1] - 1;
int move = rot[i + 1] - rot[i];
for (int j = l; j <= r; j++) {
int T = t;
T -= j - l;
ans[md(n, j + ((T - 1) / move + 1) * move)] = j;
}
}
for (int i: ans) cout << i << ' ';
}
다른 풀이Permalink
초마다 개가 오른쪽으로 쉬프트된다고 생각하지 말고, 모든 소들이 쉬프트 된다고 생각하자.
그럼 의 소들은 계속 왼쪽으로 가며 젤 왼쪽의 소는 로 한 이동마다 변경된다.
따라서 를 이 구간의 길이로 나머지연산하여 최종 소의 위치를 결정하고 왼쪽으로 밀었으므로 정답엔 번 오른쪽으로 밀어서 출력한다.
void solve() {
int n, k, t;
cin >> n >> k >> t;
vi rot(k);
fv(rot);
rot.pb(n);
vi ans(n, -1);
for (int i = 0; i < k; i++) {
int l = rot[i], r = rot[i + 1] - 1;
int L = r - l + 1;
for (int j = l; j <= r; j++) {
int nxt = j - t % L;
if (nxt < l) nxt += L;
ans[nxt] = j;
}
}
vi copy(n);
for(int i = 0 ; i < n ; i++) copy[md(n, i + t)] = ans[i];
for (int i: copy) cout << i << ' ';
}
Comments