백준 (226) 썸네일형 리스트형 백준 2056 - 작업 작업 간 선행관계가 제시되어 있으므로 작업들의 관계는 DAG가 되고 DP를 통해 각 작업을 끝내는데 필요한 최소시간을 찾아 더해주면 된다. 포레스트 형태에 대해 유의하여 구현한다. 전체 코드 더보기 #include using namespace std; using graph = vector; int finished[100001]; int fee[100001]; int memo[100001]; int dp(int node, graph &al); int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); int n; cin >> n; memset(memo, -1, sizeof memo); graph task(n + 1); for (int i = 0;.. 백준 1285 - 동전 뒤집기 www.acmicpc.net/problem/1285 N×N으로 놓여진 동전을 한행씩, 한열씩 뒤집을 수 있을 때 T의 갯수를 최소화 하는 문제이다. 이 문제는 2N 완전탐색을 통한 전처리 후 나머지를 그리디하게 결정하는 방법으로 풀 수 있다. 각 행을 뒤집는 경우를 완전탐색으로 결정한다고 해보자. 각 행에 대해 뒤집을지 말지 결정하는 경우의 수를 2N의 시간 복잡도로 찾을 수 있다. 각 행에 대해 뒤집는 연산이 끝나면 각 열에 대해 뒤집었을 때와 뒤집지 않을 때의 T의 개수를 비교하여 T가 더 적은 쪽을 선택해나가는 방식으로 답을 구할 수 있다. 행이 아니라 열을 뒤집는 경우에 수에 대해 탐색하고 각 행을 뒤집을지 결정해도 상관없다. 총 시간복잡도는 O(2NN2) 가 된.. 백준 17420 - 깊콘이 넘쳐흘러 www.acmicpc.net/problem/17420 개인적으로 이 문제는 지문이 난해하다고 생각한다. 지문을 정리하면 사용 기한이 Ai일 남은 기프티콘을 Bi일 후에 쓸 계획인데 기프티콘을 한번 연장하면 30일 연장이 된다. 기프티콘을 쓸 때는 사용 기한이 제일 촉박한 기프티콘을 먼저 사용한다. 기한이 가장 적게 남은 기프티콘이 여러개면 아무거나 사용할 수 있으며 하루에 여러 기프티콘을 쓰거나 연장할 수 있다. 기프티콘을 모두 사용하는 최소 연장 횟수를 구하라. 문제를 푸는데 핵심인 부분은 입력에 써있는 설명과 '기프티콘을 쓸 때는 사용 기한이 제일 촉박한 기프티콘을 먼저 사용한다. 기한이 가장 적게 남은 기프티콘이 여러개면 아무거나 사용할 수 있으며 하루에 여러 기프티콘을 쓰거나 연장할 수.. 백준 1082 - 방 번호 www.acmicpc.net/problem/1082 가지고 있는 돈으로 만들 수 있는 가장 큰 수를 출력해야 한다. 0을 제외하고 0으로 시작하는 수가 없다고 한다. 이 문제는 양의 정수와 관련하여 다음과 같은 성질을 생각할 수 있다. 1. 자릿수가 많을수록 큰 수이다. 2. 어떤 두 수를 비교할 때 자릿수가 같다면 가장 앞에 자리가 큰 수가 더 크다. 이 두 성질을 통해 이 문제의 최적해를 구하기 위해서는 첫번째 숫자가 0이 되서는 안된다는 규칙을 지키면서 자릿수를 가능한한 크게 늘려야 하고, 자릿수를 늘릴 수 없다면 그 상태에서 수를 가장 크게 만들어야 한다. 이는 가장 싼 가격의 숫자를 최대한 많이 사서 자릿수를 늘리고 (첫번째 숫자는 0이 될 수 없다는 규칙을 지키면서) 자릿수를 최대한 늘리고 남.. 백준 14400 - 편의점 2 www.acmicpc.net/problem/14400 새로 세우려는 편의점과 모든 주요 고객들의 맨하탄 거리가 최소가 되는 값을 찾아야 한다. 일직선 그래프의 경우에 대해 먼저 생각해보자. 일직선 그래프에서 모든 정점들과의 거리가 최소가 되는 좌표는 가운데에 위치한 점, 좌표들의 중앙값일 것이다. 이를 평면 그래프로 확장하면 X축에서 x좌표의 중앙값과 Y축에서 y좌표의 중앙값이 맨하탄 거리의 합을 최소로 하는 좌표가 된다. 정렬을 통해 각 축의 중앙값을 찾아 좌표를 만들고 해당 좌표와 고객들 사이 맨하탄 거리를 더해주면 답이 나온다. 전체코드 - 값이 int 범위를 넘어섬에 유의하자. #include using namespace std; using ll = long long; bool cmp(pair &.. 이전 1 ··· 37 38 39 40 41 42 43 ··· 46 다음 40/46
