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/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net N이 15로 작은편에 속하기 때문에 O(2^N) 브루트포싱을 사용해서도 문제를 해결할 수 있다. 브루트포스의 구현을 위해서 비트마스킹을 사용해줬다. i번 비트가 켜진 경우가 i번 식재료를 선택하는 경우이다. 문제에서 까다로웠던 부분은 같은 비용의 집합이 하나 이상이면 사전 순으로 가장 빠른 것을 출력한다. 였는데, 정답이 담긴 벡터들을 관리할 vector 구조를 하나 만들어서 정답 배열들이 담긴..
우선순위가 특별한 DFS이다. https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 방문 순서에 맞게 DFS로 탐색할 수 있는지 체크해야 하는 문제. 방문 순서에 맞게 탐색시키기 위해서, 방문 순서를 "우선순위" 화 시켜서 탐색할때 우선순위가 가장 높은 == 방문 순서에 가장 가까운 형태로 DFS를 진행하면 된다. 방문 순서를 관리하는 배열을 만들고 정렬 시에 참고하도록 하게 작성해서 해결했다. DFS 함수는 문제..
깔끔하게 풀어서 마음에 드는 문제. https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 음수 위치의 책을 집고 양수 위치의 책을 또 집는것은 이동거리의 낭비가 되기 때문에, 음수 위치에 있는 책들끼리 묶어서 옮기고 양수 위치에 있는 책들끼리 묶어서 옮기려는 생각을 해야 한다. $M$개씩 묶어서 옮기는 과정에서, 이동거리는 묶인 것들 중 가장 절댓값이 큰 숫자의 두배(왕복) 이 된다. 제일 마지막에는 다시 0으로 돌아올 필요가 없고, 왕복하느라 이미 제일..
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들의 합으로 구성한다고 할 ..