DP + DFS https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net dp[x][y] 를 (x,y)에서 판다가 먹기 시작할때 지날수 있는 위치의 최대값으로 만들어주면 쉽게 해결할 수 있다. 이 dp[x][y]를 구하기 위해서는 주변 네칸을 탐색 후 dp[nx][ny]가 구해지지 않았다면 이 또한 구해주는 DFS를 이용하면 AC를 받을 수 있다. #include using namespace std; int dx[] = {-1, 1, 0, 0..

어째 구데기만 골라풀고있는거같은 느낌이 든다.... 이번에는 map을 사용하거나 unordered_map을 사용하면 TLE를 받는 문제다. 답은 벡터를 정렬해서 이분탐색. 답을 안까보면 이런건 모르잖아요 ㅠㅠㅠㅠㅠ 코드포스에서 hack할때 map을 자주 이용한다고 들었는데 이걸 당할줄은 몰랐다;; https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 4000^4 는 TLE가 나게 될 것이므로 4000^2의 갯수를 가지는 두개의 벡터..

"네트워크"에서 감을 잡고 유니온-파인드임을 알아내면 나머지는 무난무난하다. https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net map을 통해서 string -> int로 변환해주는 과정이 필요하다. 변환해준다음에는 그냥 union 한번 해주고 부모노드 두개에 대한 친구 네트워크의 수의 최댓값을 찾으면 된다. 어제 fastio 로 맞왜틀을 경험하고 fastio를 써보려고 하고 있다. #include using namespace std; ..

역대급으로 어이없는 문제..... https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net priority_queue와 fastio의 조합이라는 말도안되는 정답을 요구한다 printf / scanf -> TLE cout / cin with fastio -> AC ???????? 맞춰놓긴 했는데 왜이런진 아직도 모르겠다. 인덱스를 저장해두고 최솟값을 꺼낼때 인덱스 범위를 충족하는지 확인해주면 되는 문제였다. 아마 이런거 보..

오일러 피 함수의 구현과 그 응용 문제 https://www.acmicpc.net/problem/19577 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net 모든 수에 대해서 xF(x) 를 구하려 하면 TLE 가 발생한다. 이를 해결하기 위해서는 x도 정수, F(x)도 정수임을 이용해 x에 들어갈 수를 N의 약수로 한정지으면 문제를 해결할 수 있다. 그리고 N==1일때 코너케이스가 발생해 이부분을 따로 처리해주었다. #include using namespace std; typedef long long int ll; map prime; vector v; int main(){ ll n; scanf("..

오일러 피 함수의 구현 오일러 피 함수는 주어진 수를 소인수분해한뒤 소인수분해된 수들을 다음과 같은 규칙에 따라 계산하면 된다 P(소수) = A^a * B^b * C^c ...... f(P) = (A^a - A^(a-1) * (B^b - B^(b-1)) ...... 그럼 이제 이 문제는 주어진 수를 빠르게 소인수분해하는 문제가 된다. https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net #include using namespace std; typedef long long int ll; map pr..

nlogn lis의 경로추적 반전 문제. https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net lis잘 구해서 역추적 해준 다음에 역추적해서 나온 값들 정렬해주고 입력 배열과 비교해가며 없는애들을 따로 관리해주면 된다. #include #define INF 123456789 using namespace std; vector lis; vector v; vector back; int chk[567890] = {0}; int conv[567890] =..

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net lis nlogn구현과 함께 역추적이 가능한지를 묻는 문제였다 일단 처음으로 문제에 접근했던 방법은 각 자리 lis배열의 최솟값을 저장하는건데 이건 WA가 나왔었고, 반례를 접하고 나서의 접근은 일단 lis의 그 끝 값을 구성하는 수가 나온 뒤에 이보다 작은 값이 나올때 순서대로 채워나가는 것이었다. 즉 for문을 통해 역순회하면서 정답 배열또한 역순으로 채워주면 된..

LIS NlogN 연습의 전형적 형태 입력이 간단해서 쉬웠다. https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 풀이방법은 정말 lis 구현밖에 없다.... #include #define INF 123456789 using namespace std; vector v; vector in; int main(){ int n,tmp; scanf("%d", &n); for(int i=0; i

오버킬 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net lis의 nlogn이 주제였으므로 의도치않게 오버킬을 했다. 입력받은 값을 pair에 넣고 정렬 후 lis구하기. #include #define INF 123456789 using namespace std; vector v; vector input; int main(){ v.push_back(-INF); int n,a,b; scanf("%d", &n); for(int i=0; i