본문 바로가기

전체 글327

BOJ 16562 - 친구비 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N) 다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. www.acmicpc.net 유니온파인드 문제다. 각 집합의 최소를 모두 더한 합을 출력하면 된다. #include #include using namespace std; int n, m, k; int uf[10001]; int cost.. 2019. 8. 6.
BOJ 2075 - N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 라이님블로그의 풀이를 리뷰. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; priority_queue pq; //최소힙 for (int i = 0; i < n; i++) { for (int j = 0,a;.. 2019. 8. 6.
BOJ 1351 - 무한 수열 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 개인적으로 매우 신박한 문제다. 대놓고 기본 dp문제인데 dp배열로 풀기엔 배열 크기가 오버된다. map을 사용해서 dp하는 문제다. #include #include #include using namespace std; map dp; long long n, p, q; long long f(long long n) { if (n == 0)return 1; auto ret = dp.find(n); if (ret != dp.end()) return ret->second; long long rst = 0; rst = f(n / p) + f(n / .. 2019. 8. 6.
BOJ 1949 - 우수마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다. www.acmicpc.net #include #include #include #include using namespace std; int N, val[10000], dp[10000][2]; vector adj[10000], child[10000]; bool visited[10000]; void setChildr.. 2019. 8. 6.

티스토리툴바