사탕 돌리기 (JUNGOL 4603)

https://jungol.co.kr/problem/4603?cursor=IjEzIiwzLDQ=

---

아이디어

잘 생각해보면 어떤 위치에서 그 위치가 아닌 사탕을 하나 들고 그 사탕의 위치로 가면, 그 위치에도 그 위치가 아닌 사탕이 적어도 하나 존재합니다. 이렇게되면 하나의 사이클이 존재하게 되는데, 여러개의 사이클을 적절히 연결하면 하나의 사이클로 연결할 수 있게 됩니다. 그러므로 모든 사탕을 이동시키는데에 아무것도 안들고 이동하는 경우 없이 배열할 수 있습니다.

 

이때 만약 1번 깡통에 1번 사탕만 존재한다면, 시작을 제때 하지 못하므로 전체 돌아야하는 회전수에 1을 더해주어야합니다.

 

만약 K번에 사탕을 배열할 수 있다면, 그냥 1을 들고 한바퀴 돌아서 K+1번에 사탕을 배열할 수 있습니다. 그러므로 최소 회전수가 Q이하인지만 확인해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,K,Q,i,j,x,res=0;
    bool AllRight=true;

    cin>>N>>K>>Q;
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=K;j++)
        {
            cin>>x;

            if (i==1 && x!=i) AllRight=false;
            if (x>=i) res+=x-i;
            else res+=N+(x-i);
        }
    }

    res/=N;

    if (res!=0 && AllRight) //옮겨야할것이 있지만 1번 칸에는 없을때
        res++;

    cout<<(res<=Q);
}