www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표 압축 문제는 테크닉은 어렵지 않지만 더 어려운 문제에서 활용되어 쓰인다고 한다. 처음에는 pair를 사용해서 인덱스와 값을 입력받고 정렬 후 O(N)으로 처리하려 했는데 잘 안돼서 찾아보니 unique와 lower_bound를 사용해서 해결하는 문제였다. 우선 배열 2개를 선언해서 같은 값을 받아준다. vector ar(n), ans(n); for (int..

www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 팰린드롬 수는 어떤 수를 반대로 뒤집고 그 수가 같다면 팰린드롬 수이다. 에라토스테네스의 채를 사용해서 소수를 판단해주고 문자열을 사용해서 뒤집고 체크해주면 되는 쉬운 문제였다. #include #include #include #include using namespace std; vector sieve(1100001); void era(int n) { fill(sieve.b..

www.acmicpc.net/problem/2086 2086번: 피보나치 수의 합 첫째 줄에 a와 b(1≤a≤b≤9,000,000,000,000,000,000)이 주어진다. www.acmicpc.net a번째 피보나치 수~b번째 피보나치 수의 합을 구하는 문제다. a부터 b까지 모든 피보나치 수의 합을 하나씩 구해서 더하면 O(N) 이므로 a가 1이고 b가 9e18 일 경우 무조건 시간 초과... 따라서 간단한 관찰을 통해 식을 구해야 한다. 1부터 10까지 전부 적어보면 1 2 3 4 5 6 7 8 9 10 1 1 2 3 5 8 13 21 34 55 인데 \(F_5\) 부터 \(F_7\) 까지 구해보면 합은 26이고 이는 \(F_9-F_6\) 인 것을 알 수 있다. 일반화해보면 $$F_{a \;to\;..

www.acmicpc.net/problem/11778 11778번: 피보나치 수와 최대공약수 첫째 줄에 n과 m이 주어진다. n과 m은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 문제들을 풀면서 비슷한 유형들 여러 가지를 푸는데 상당히 재미있다. 이번 문제는 행렬 제곱을 이용한 큰 수의 피보나치 수를 구해서 최대공약수를 구하는 것이다. 이 문제는 각각 n과 m에 대해서 피보나치 수열을 구하고 그 수의 최대 공약수를 구해도 되지만 n과 m을 미리 최대공약수를 구한 뒤 그 수의 피보나치 수를 구해도 된다. #include #include using namespace std; using ll = unsigned long long; const..

www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번에는 나누는 값이 1000000007이다. www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제에서는 나누는 값이 백만이라 피사노 주기를 통해서 구할 수 있었지만 이번 문제에서는 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. 조건 때문에 피사노 주기를 구하려면 시간 초과가 날 ..

www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번엔 피보나치 수 3을 풀어봤다. 입력받는 N이 무려 \(10^{18}\) 이다... 내가 알기에 Long Long int 형이 딱 저 자릿수에 걸치는 걸로 안다. 이 문제는 피사노 주기를 이용해서 풀어야 한다. 피보나치 수열은 어떤 값으로 나눌 경우 특정한 주기를 갖는데 이 문제에서는 나누는 값이 백만으로 매우 작아서 피사노 주기를 이용하여 풀 수 있다. do { int tmp = m1; m1 = m2; m2 = (tmp + m1) % MOD; len++; } while (m1 != 0 ..