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/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..