백준 (227) 썸네일형 리스트형 [KOI] 백준 2638 - 치즈 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net KOI 중등부 치즈문제이다. 중등 치즈에서는 치즈 격자가 외부 공기와 두변 이상 접촉해야 녹는다고 하며 치즈를 모두 녹이는데 필요한 시간을 구해야 한다. 또한 모눈 종이에 가장자리에는 치즈가 놓이지 않는다는 조건이 있다. 이를 공기의 관점으로 접근하면 문제를 해결할 수 있다. 1. BFS로 공기를 흘려보낸다. 가장자리에는 치즈가 놓이지 않으므로 탐색 시작점은 (0, 0)이 적절할 것이다. 공간을 탐색하.. 백준 1758 - 알바생 강호 www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수 www.acmicpc.net 고객이 기다리는 순번이 하나 증가할수록 주려는 팁에 패널티가 1씩 생길 때(역으로 돈을 갈취하지는 않는다.), 강호가 가장 많이 팁을 벌 수 있도록 하여 고객을 배치할 때 벌어들이는 팁을 구하는 문제이다. 높은 금액의 팁을 주는 고객일수록 적은 패널티를 받게 해야 최적해에 이를 수 있다. 따라서 팁을 많이 주는 순서대로 내림차순 정렬하여 받을 수 있는 팁을 계산하면 최적해를 구할 수 있다. .. [ICPC] 백준 17521 - Byte Coin www.acmicpc.net/problem/17521 자본금으로 얼마나 많은 수익을 얻을 수 있을지 구하는 문제이다. 바이트 코인 예측 금액을 나열한 차트를 단조 감소하는 구간과 단조 증가 하는 구간으로 분리하여 단조 감소를 만족하는 마지막 날에 풀매수하고 단조 증가를 만족하는 마지막 날에 풀매도하면 최대 이익을 얻을 수 있다. 단조 감소 구간을 추적하는 L 포인터와 단조 증가 구간을 추적하는 R 포인터를 통해 최적 매수/매도 날짜를 탐색한 후 이를 계산하는 방식으로 구현했다. 전체 코드 더보기 #include using namespace std; using ll = long long; int main() { int days; ll seed; cin >> days >> seed; if (days == 1.. 백준 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][.. 이전 1 ··· 39 40 41 42 43 44 45 46 다음
