전체 글 (343) 썸네일형 리스트형 백준 15468 - 퇴사 2 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 상담을 통해 백준이가 얻을 수 있는 최대 수익을 구해보자. N이 최대 150만으로 꽤 크므로 완전탐색은 불가능하고 동적 계획법을 통해 문제를 풀어야 한다. 다음 점화식을 세워 풀이할 수 있다. 구하려는 최대 수익 earning에 대해 earning += max(idx 일에 상담을 실시 했을 때 벌 수 있는 수익, idx 일에 상담을 하지 않을 경우 벌 수 있는 수익) 본인의 코드에.. 백준 13977 - 이항 계수와 쿼리 www.acmicpc.net/problem/13977 최대 10만 개의 쿼리에 대해 (nr) mod 109+7 을 구해야 하는 문제이다. N과 K는 400만 이하이기 때문에 이항 계수 DP나 일반적인 반복문 연산으로는 제한 메모리/시간 내로 10만개의 쿼리를 처리할 수 없다. 알아야 할 것 이 문제를 해결하기 위해선 페르마의 소정리를 이용해야 한다. 페르마의 소정리 : 소수 p가 있고 정수 a가 p의 배수가 아닐 때 다음이 성립한다. ap≡a (mod p) 페르마의 소정리를 통해 문제에서 요구하는 것을 빠르게 계산할 수 있다. 방법 일단 이항계수를 제곱식으로 바꾸면 다음과 같이 된다. $\binom{n}{r} = \frac{n!}{(n - r)!.. [USACO] 백준 5864 - Wifi Setup www.acmicpc.net/problem/5864 일직선상에 서있는 N(1 n >> a >> b; dp[0] = a; for (int i = 0; i > x; crd.push_back(x); } sort(crd.begin(), crd.end()); cout 백준 1744 - 수 묶기 https://www.acmicpc.net/problem/1744 두 수를 곱할 수 있을 때 주어진 수들의 최대 연산값을 구하라는 문제이다. 예시를 주의깊게 보도록 하자 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다. 그냥 Σarr를 할 때보다 큰 수들을 곱한 후 더해주어서 최대 연산값을 이끌어내는 것을 볼 수 있다. 설명한 예시를 통해 가능한한 수들을 많이 곱하는 것이 답을 도출하는 길임을 알 수 있다. 그러면 주어진 수들을 모두 두개씩 곱해 다 더해버리면 되는 게 아닐까? 결코 아니다. 다음과 같은 테스트 케이.. 백준 1976 - 여행가자 https://www.acmicpc.net/problem/1976 최대 200개의 도시 수가 인접행렬 형태로 주어진다. 문제에서 주어진 여행지들을 모두 여행할 수 있는지 판단할 것을 요구하고 있다. 즉 주어진 도시들이 연결되었는지를 판단하면 되므로 두가지의 풀이를 생각할 수 있는데 첫번째는 플로이드 워셜 알고리즘을 이용하여 쉽게 구하는 방법이고 두번째는 유니온 파인드를 이용해 각 정점들이 연결되어 있는지 판단하는 방법이다. 이 풀이에서는 유니온 파인드를 이용해보겠다. DisjointSet st(n); int loop; cin >> loop; for (int i = 0; i > connex; if (con.. 이전 1 ··· 65 66 67 68 69 다음 68/69
