본문 바로가기

백준

 (223)
백준 1311 - 할 일 정하기 1 www.acmicpc.net/problem/1311 어렵지 않은 비트마스크 dp이다. 다음 dp테이블을 정의하고 탑 다운 dp로 풀면 된다. dp[i] = 비트마스크 i의 조합으로 일을 할당했을 때 비용의 최솟값 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include using namespace std; int n; int ar[20][20]; int dp[1 n; for (int i = 0; i ar[i][j]; memset(dp, -1, sizeof dp); int res = 1e9; for (..
백준 12845 - 모두의 마블 www.acmicpc.net/problem/12845 가치가 가장 큰 카드가 인접한 카드들을 잠식해나가면 최대 골드를 얻게 된다. 가치가 가장 큰 카드를 찾고 나머지 카드들을 문제 조건에 맞게 모두 더해주자. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include using namespace std; int ar[1000]; int n; int res; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (int i = 0; i > ar[i]; sort(ar, ar + n); for (int i = n - 2; i >= 0; --i) res += ar[n - 1] +..
[KOI] 백준 2437 - 저울 www.acmicpc.net/problem/2437 예제에 주어진 추들을 정렬하고 무게들을 더하다 보면 무게가 30인 추를 넣을 때 지금까지 더한 무게 20과 거기에 30을 더한 무게 50 사이의 무게를 만들 방법이 없어 답은 21이 되는 것을 관찰할 수 있다. 즉 정렬된 추들의 무게를 누적 합으로 저장하면서 현재 추가할 추의 무게가 누적 합 범위 안에 들어온다면 누적합에서 현재 추를 더한 범위 내의 무게를 만들 수 있다고 생각할 수 있다. 그렇지 않다면, 즉 추가할 추의 무게가 누적 합 + 1 범위를 벗어난다면 답은 지금까지 더한 누적 합 + 1이 된다. 왜 누적 합 + 1이냐면 추가할 추의 무게가 누적 합 + 1일 경우 누적 합 + 1은 추가할 추 한개로 무게를 잴 수 있기 때문에 그보다 큰 범위를 ..
[ICPC] 백준 1700 - 멀티탭 스케줄링 www.acmicpc.net/problem/1700 풀이 정해는 OS분야에서 고안되었으나 사용하지 못하는 최적 페이지 교체 알고리즘이다. 멀티탭이 가득 찼을 때 꽃힌 전기용품 중에서 가장 늦게 사용될 물건을 빼버린다는 것인데 이 말은 전체에서 마지막으로 나타나는 전기용품이 아니라 다음에 쓸 전기용품 중 처음으로 등장했을 때 그 순서가 가장 늦은 용품을 빼는 것이다. 물론 더이상 쓰지 않을 물건은 최우선으로 빼줘야 한다. 구현 어떤 용품의 사용횟수가 얼마나 남았는지 mp배열로 저장해준다. 멀티탭에 어떤 용품이 꽃혔는지 셋으로 관리하면서 멀티탭이 가득차지 않았거나 꽃혔던 물건을 사용한다면 해당 용품을 셋에 삽입하여 넘어간다. 플러그를 뽑아야만 한다면 먼저 사용을 다 한 물건이 있는지 확인해주고 그렇지 않다면..
백준 1021 - 회전하는 큐 www.acmicpc.net/problem/1021 덱에 들어있는 원소의 정확한 내용물은 정해지지 않았으므로 원소의 순서로 붙여진 숫자를 원소라 봐도 무방하다. N과 M이 크지 않으므로 각 원소를 제거하기 위해 왼쪽으로 회전하는 경우, 오른쪽으로 회전하는 경우를 나눠 둘 중 연산 횟수가 적은 쪽을 택하면 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include using namespace std; int n, m; deque dq; int cnt; int main() { ..

티스토리툴바