[C++] 기념품 (백준 12873번)

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

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n ; i++) a[i] = i + 1;

    long long idx = 0;
    int curn = n;
    for (int i = 1; i < n; i++) {
        long long tmp = (long long) i * i * i - 1;
        idx = (idx + tmp) % curn;
        a.erase(a.begin() + idx);
        curn--;
    }

    cout << a[0] << '\n';
}

태그는 큐인데 나는 그냥 vector와 erase 함수를 사용했다. 

근데 여기서 주의할 점이 두 가지가 있다. (내가 여러번 틀린 이유...)

1. cmath에 있는 pow(i, 3)를 사용하면 값이 의도대로 나오지 않을 수 있다. pow의 반환값이 double이라서 int로 바꾸는 과정에서 문제가 생길 수 있기 때문이다. 그래서 i * i * i 를 사용하였다. 

2. idx, tmp 뿐만 아니라 i * i * i 앞에도 long long을 붙여 줘야 한다. i가 int 이기 때문에 long long을 붙이지 않으면 i * i * i 에서 오버플로우가 날 수 있다. 

이 두 가지만 주의하면서 주어진 대로 구현하면 되는 문제였다. (AC)