[cpp 알고리즘] 백준 17827 달팽이 리스트

[백준] 17827 달팽이 리스트 cpp(c++) 풀이

알고리즘: 수학, 구현

https://www.acmicpc.net/problem/17827

문제 요약

- 선형 단방향 연결리스트로 1번 부터 N번 노드까지 연결되어 있다.

- 이 때, N번 노드가 1번 노드를 제외한 임의의 노드를 가리켜 사이클을 생기는 연결 리스트를 이룬다. 

- 이 때 K번 노드에는 어떤 값이 있을지 구하는 문제이다. 

풀이 정리

- 연결리스트가 된 이후에 K번째 값들을 나열해 보았고, 아래와 같은 수식을 얻을 수 있었다.

- k번째 값이 (V-1)보다 작으면 (=연결되지 않는 부분)이면 해당 인덱스의 값을 출력해주면 된다.

- 그 외의 경우는, 반복되기 때문에 V번째로부터 (K-(V-1)) % (N-(V-1)) 만큼 떨어져 있는 값을 출력해주면 된다. 

백준 17827 풀이

C++ 코드

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

ll N, M, V;
ll arr[MAXN];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N >> M >> V;
    
    for(int i=0; i<N; i++){
        cin >> arr[i];
    }
    
    while(M--){
        ll find; cin >> find;
        
        if(find < (V-1)){
            //0인 경우 예외처리
            cout << arr[find] << "\n";
        }
        else{
            ll index = (find-(V-1))%(N-V+1);
            //cout << index << "값: ";
            cout << arr[V-1+index] << "\n";
        }
    }
    
    return 0;
}

시간초과

ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

- 시간초과가 발생해서 입/출력 단축 코드를 추가하니까 문제가 해결되었다.