와드의 블로그

문제N마리의 소가 길을 건너려고 합니다. 소는 한 번에 한 마리씩만 길을 건널 수 있으며, 각 소가 도착한 시간과 길을 건너는 데 걸리는 시간이 주어집니다. 모든 소가 길을 건너는 데 걸리는 최소 시간을 구하는 문제입니다.입력: 첫째 줄에 소의 수 N (1 ≤ N ≤ 100)이 주어집니다. 둘째 줄부터 N개의 줄에 각 소가 도착한 시간과 길을 건너는 데 걸리는 시간이 주어집니다.출력: 모든 소가 길을 건너는 데 걸리는 최소 시간을 출력합니다.링크: https://www.acmicpc.net/problem/14469풀이이 문제는 소들이 도착한 순서대로 길을 건너게 하는 것이 가장 효율적입니다. 따라서 도착 시간을 기준으로 오름차순 정렬한 뒤, 소요 시간을 누적해 나가는 그리디 방식을 사용합니다.객체 생성 ..

문제n개의 정수로 이루어진 임의의 수열이 주어집니다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 합니다. 단, 숫자는 적어도 하나 이상 선택해야 합니다.입력: 첫째 줄에 정수 n (1 ≤ n ≤ 100,000)이 주어지고, 둘째 줄에 n개의 정수로 이루어진 수열이 주어집니다.출력: 첫째 줄에 가장 큰 연속합을 출력합니다.링크: https://www.acmicpc.net/problem/1912풀이: 다이나믹 프로그래밍 (DP)이 문제는 이전까지의 계산 결과를 활용하여 현재의 최적해를 구하는 전형적인 다이나믹 프로그래밍(DP) 문제입니다. (카데인 알고리즘과 동일한 원리입니다.)DP 배열 정의: d[i]를 i번째 원소를 마지막으로 포함하는 연속 부분 수열의 최..

문제식재료 N개 중에서 몇 개를 선택해서 단백질, 지방, 탄수화물, 비타민의 합이 주어진 최소 영양소 기준을 만족하도록 할 때, 그 비용의 최솟값을 구하는 문제입니다. 조건을 만족하는 최소 비용 조합이 여러 개라면, 그중 사전 순으로 가장 빠른 것을 출력해야 합니다.입력:첫째 줄: 식재료의 개수 N (3 ≤ N ≤ 15)둘째 줄: 단백질, 지방, 탄수화물, 비타민의 최소 요구량셋째 줄부터 N개의 줄: 각 식재료의 단백질, 지방, 탄수화물, 비타민, 가격출력: 조건을 만족하는 최소 비용과 선택된 식재료 번호들을 오름차순으로 출력. 만족하는 경우가 없으면 -1 출력.링크: https://www.acmicpc.net/problem/19942풀이 1: 비트마스킹 (Bitmasking)을 활용한 부분 집합 탐색식..