https://www.acmicpc.net/problem/1990 1990번: 소수인팰린드롬 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되 www.acmicpc.net 입력으로 들어오는 수의 범위가 적절하게 커서 O(N) 내지 O(Nsqrt(N)) 으로는 해결할 수 없다. b의 범위가 최대 1억이고 1억은 팰린드롬 숫자가 아니므로, 문제에서 요구하고 있는 "최대 8자리의 팰린드롬 수" 는 앞뒤가 똑같다는 특성 때문에 1만개보다 많지 않으므로, 1부터 1만까지 순회하면서 이 수가 뒤에도 반복되는 팰린드롬 수를 직접 만들어주면 된다. 나는 문자열로 변경..
https://www.acmicpc.net/problem/1769 1769번: 3의 배수 문제가 잘 풀리지 않을 때, 문제를 바라보는 시각을 조금만 다르게 가지면 문제가 쉽게 풀리는 경험을 종종 해 보았을 것이다. 여러 가지 방법이 있지만 그 중 하나로 우리가 풀고 싶은 문제를 www.acmicpc.net 범위 잘못봐서 틀렸던 문제. 첫 입력을 문자열로 받아야 함에 유의하자. 첫 입력을 받아서 Y를 만들어 내면, Y의 범위는 900만 이하이므로 int범위 안에 저장할 수 있으니 오버플로우에 대해서는 걱정하지 않아도 된다. 나는 만든 Y를 다시 X에 저장하는 방법으로 구했다. #include using namespace std; int main(){ string s; cin >> s; int cnt = 0..
https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net 그리디 알고리즘을 사용한다. 문제 지문을 관찰해보면 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실 이라는 언급이 있다. 이를 통해서 유추해 볼 수 있는 사실으로, 어떠한 수 K에서 피보나치 수 F를 빼서 k를 만들면, 그 새로운 수 k도 다시 피보나치 수들의 합으로 나타낼 수 있다는 것을 알 수 있다. 어떠한 수를 피보나치 수 F들의 합으로 구성한다고 할 ..
https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 정렬 문제. 현재 단계에서 K명이 정렬을 진행할때, 사람 혼자서 맡게되는 부분 배열의 크기는 N/K 이다. 전체 N개 크기의 배열을 N/K 개의 부분 배열로 분할해서, 그 부분만 정렬해주면 된다. 정렬에는 std::sort을 사용했다. #include using namespace std; int N,K; int arr[1234567] = {0}; int main(){..
https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 입력으로 들어오는 정수 A를 숫자가 아니라, '0' 부터 '9' 까지의 문자가 들어오는 문자열로 보면 이 문자열 배열에 대해서 next_permutation 을 통해서 순서를 섞어낼 때의 모든 조합을 구할 수 있다. 모든 순서를 찾아보는 시간복잡도는 O(N!) 이고, A는 10^9보다 작은 수이기 때문에 최대 9자리라서 N=9 이다. 이때의 계산 횟수는 대략 40만언저리쯤 ..
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net DP로 해결했습니다. dp[i][j] 를 문자열 A를 i번 인덱스까지 자르고, 문자열 B를 j번 인덱스까지 잘랐을 때 두 문자열의 공통 접미사의 길이 로 정의한다. 이제 이 dp 배열을 O(N^2) 로 순회하면서 채우는데, 만일 A[i] 와 B[i]가 서로 같다면 A[i-1]과 B[i-1] 도 서로 비교해 보아야 한다. 이때, dp[i-1][j-1] 이 공통 접미사의 길이를 이미 저장하..