boj
-
1017번 : 소수 쌍알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 31. 16:11
https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 집합에 속한 임의의 원소 두개의 합이 소수가 되도록 모두 짝지었을 때 첫 번째 원소와 짝지은 원소들을 오름차순으로 출력하는 문제다. 아이디어, 구현 : 네트워크 플로우(이분매칭)으로 해결할 수 있었다. 하지만 조금 특이한 방식으로 해결했다. 먼저, 모든 수를 두개로 늘려서 짝지을 첫번째 원소, 짝지을 두번째 원소로 나누었다. 첫 번째 원소는 제외하..
-
2123번 : 인간 탑 쌓기알고리즘/백준(acmicpc.net) 문제풀이 2022. 1. 29. 14:11
https://www.acmicpc.net/problem/2123 2123번: 인간 탑 쌓기 N (1 ≤ N ≤ 50,000) 명의 곡예사들로 인간 탑을 쌓으려고 한다. 한 사람이 한 층을 이루게 되어, 탑은 총 N층이 된다. 어떤 층에 있는 사람은 그보다 높은 층에 있는 모든 사람들의 몸무게의 합만큼 www.acmicpc.net 곡예사들의 위험도 중 가장 큰 값이 가장 작아지게 배치하는 문제이다. 아이디어 : 주어진 곡예사들 중 가장 밑에 깔릴 하나를 구해야 한다는 느낌으로 접근한다. 모든 곡예사들에 대해 만약 그 곡예사가 가장 밑에 깔린다면 위험도는 얼마나 될지 구해본다. 구한 위험도 중 가장 작은 값을 갖고 있는 곡예사가 가장 밑에 깔린다. 밑에 깔린 곡예사는 이제 제외시키고 남은 곡예사들 중 가장..