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들의 합으로 구성한다고 할 ..

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] 이 공통 접미사의 길이를 이미 저장하..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net DP 사용해서 해결했다. dp[i] 를 i일째 시점에서 상담을 끝냈을 때의 최대 이익으로 정의한다. i일째에 상담을 진행한 경우는 dp[i+T[i]] 를 dp[i] + P[i] 로 갱신 할 수 있으며, 이때 편의상 T[i]와 P[i] 를 0부터 시작하는 인덱스로 관리해주면 소스코드가 깔끔해진다. 상담을 진행하지 않더라도, 지난 일자에서의 최대 수익을 그대로 가져와서 ..