백준 10739번 KRIZA

문제 링크입니다: https://www.acmicpc.net/problem/10739

사이클과 모듈라 연산을 적절히 이용해서 풀어야하는 문제였습니다.

종이에 그려보면서 수학적으로 접근한다면 그렇게 어려운 문제는 아니지만 고려해야할 사항이 많기 때문에 2시간 내에 COCI A~D번 문제를 풀 때는 AC를 받지 못했던 문제였습니다.

코드의 설명은 같은 학교 학우이신 ssangba55님(https://blog.naver.com/pasdfq/221342517310)이 정말 잘 설명해주셨기 때문에 링크를 타고 가서 설명을 읽어보시는 것을 추천드립니다!

#include <iostream>

using namespace std;

 

const int MAX = 100000 + 1;

 

long long N, K, result;

long long pos[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

 

        cin >> N >> K;

        for (int i = 0; i < N; i++)

        {

                 int temp;

                 cin >> temp;

 

                 pos[temp - 1] = i;

        }

 

        //pos[i-1]에서 pos[i]까지의 거리만큼 실패(원 위에서의 시계방향 거리)

        for (int i = 0; i < N; i++)

                 result += ((pos[i] - pos[(i - 1 + N) % N] + N) % N)*(K / N + (i < K%N));

 

        //최초 한번은 fail[0]으로서 pos[N-1] ~ pos[0]의 거리가 아닌 0 ~ pos[0]의 거리

        cout << result - ((pos[0] - pos[N - 1] + N) % N) + pos[0] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~