본문 바로가기

백준

 (224)
백준 1188 - 음식 평론가 www.acmicpc.net/problem/1188 평론가들에게 같은 양의 소시지를 주기 위해 필요한 칼질 횟수의 최소를 구하는 문제이다. 알아야 할 것들 1. 가능한한 소시지는 칼질하지 않은 상태로 평론가들에게 주는게 최적해에 이를 수 있다. 즉 평론가들에게 칼질 없이 공평하게 소시지를 줄 수 있으면 답은 0이 된다. 2. 칼질을 해야 한다면 이 횟수를 줄이기 위해 소시지당 최적의 조각을 찾아야 한다. 여기에서 최적화된 소시지 조각을 찾는게 문제 해결의 핵심이다. 방법 우선 멀쩡한 소시지를 평가원에게 주고 남은 소시지와 평가원의 최대공약수를 찾는다. 남은 소시지를 최대 공약수로 나눠 몇묶음이 나올 수 있는지 regroup을 구한다. 묶인 소시지는 한개의 소시지로 친다. 그 다음 심사위원 수를 regro..
백준 14588 - Line Friends (Small) www.acmicpc.net/problem/14588 각 선분의 친분 정도를 구해야 하는 문제이다. 친구는 1, 친구의 친구는 2, 친구의 친구의 친구는 3과 같이 친분이 정의되므로 각 선분의 친분 정도는 서로 얼마나 빠르게 다가갈 수 있는지, 즉 각 선분간의 최단 경로를 구해야 하는 것으로 풀이할 수 있다. 우선 이중 for문을 통해 친분의 정도가 1인 선분의 짝을 탐색하여 그 연결을 인접행렬로 구현한다. 그 후 플로이드 워셜을 수행하여 각 선분 사이의 최단 경로를 찾는다. 그 후 질의에 따라 친분의 정도, 혹은 친구가 아닌지를 출력하면 시간 내에 AC를 받을 수 있다. 전체코드 #include #include #include #include using namespace std; int dp[300][..
백준 4796 - 캠핑 www.acmicpc.net/problem/4796 V일의 휴가 중에서 캠핑장을 최대 며칠이나 즐길 수 있을지 구하는 문제이다. 연속하는 P일 중 L일 동안 사용이 가능하다 명시했으므로 V를 P로 나누면 캠핑장을 L일동안 쓸 수 있는 횟수가 나오게 될 것이다. 이때 나머지는 min(mod, L) 계산을 통해 나머지 일 수 중에서 캠핑을 즐길 수 있는 날을 더해주면 답을 구할 수 있다. 최종 수식 $ANSWER = \lfloor V \div P \rfloor \times L + min(V mod P, L)$ 전체코드 #include #include using namespace std; using ll = long long; int main() { int l, p, v; cin >> l >> p >> v; ..
백준 12915 - 대회 개최 www.acmicpc.net/problem/12915 5개의 난이도에 해당하는 문제 수가 주어질 때 최대로 개최할 수 있는 대회의 수를 구해야 하는 문제이다. 대회를 개최하기 위해서는 쉬움, 중간, 어려움 난이도의 문제가 하나씩 배정되어야만 한다. 매개변수로 주어지는 e, m, h는 배정될 수 있는 난이도가 한가지로 정해져 있으므로 나머지 em, mh에 대해 난이도를 적절히 분배하는 방법을 찾는게 핵심이다. 방법 1. 남아있는 e, m, h를 우선적으로 배정하도록 한다. 2. 남아있는 e, m, h가 없을 경우 em, mh 중에서 배정하도록 한다. 2 - 1. 쉬움은 em을 주고 어려움은 mh를 주면 되는데 중간의 경우는 em과 mh중 더 많이 남아있는 문제를 배정하고 만약 두 난이도가 동일한 갯수만큼 ..
백준 1629 - 곱셈 www.acmicpc.net/problem/1629 $A^{B} \mod C$ 를 빠르게 구해야 하는 문제이다. 단순하게 반복문을 통해 구한다고 하면 최대 2,147,483,647번 연산해야 하므로 이는 시간 내로 해결이 불가능하다. 따라서 해결을 위해서는 다른 방법이 필요하다. 이 문제 해결에 사용되는 알고리즘은 PS를 하는데 기본 소양이 되므로 그 방법을 잘 익히도록 한다. 예시로 $2^{1024}$를 구한다고 가정해보자. $2^{1024}$는 $2^{1024} = 4^{512}$ 으로 나타낼 수 있다. 그러면 $4^{512}$도 $4^{512} = 8^{256}$ 으로 나타낼 수 있다. 이처럼 지수를 절반씩 쪼개가며 제곱하면 $O(\log n)$의 시간복잡도로 빠르게 계산할 수 있다. 지수를 절반으..

티스토리툴바