www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 정수형 배열을 입력받고 구간의 값이 팰린드롬인지 판단하는 문제다. 처음에는 문자열로 접근해서 reverse를 사용했지만 2000번에 대해서 1백만 번씩 뒤집히니 시간 초과. 결국 dp로 풀었다. #include #include using namespace std; int f(vector& d, vector& ar, int s, int e) { if (s >= e) return 1; if (d[s][e] != -1) return d[s][e]; if ..

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으로 나눈 나머지를 출력한다. 조건 때문에 피사노 주기를 구하려면 시간 초과가 날 ..