오늘은 무슨 알고리즘 문제들을 풀자! 라는 생각없이
그냥 백준 문제 목록들을 훑어보고 있었다.
근데, 이 문제가 눈에 띄었다.
https://www.acmicpc.net/problem/17528
17528번: Two Machines
문제 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti를 완료하기 위해 머신 A를 선택하면 ai시간이 걸리고 머신 B를 선택하면 bi 시간이 걸린다. 각 머신은 어느 순간에 최대 하나의 작업만 수행할 수 있으며, 한 작업이 시작되면 그 작
www.acmicpc.net
바로, 작년 ACM regional에서 내가 붙잡고 풀다가, 결국 WA떴던 문제...
regional이 끝나고 나서도, 계속해서 풀려고 했는데, 대회장에서 생각한 아이디어를 개선할 생각만하고, 새로운 아이디어가 안떠올라서 안풀고 있었던 그문제...
근데, 또 또 또 똑같이 풀고 있는 내 모습을 보고 결국 구글에게 물어보았다.
http://blog.naver.com/PostView.nhn?blogId=njw1204&logNo=221669613809
2019 ACM-ICPC 인터넷 예선 L번 (Two Machines) 리벤지 풀이
이번 인터넷 예선에서 끝내 못 풀었던 L번..너무나 아쉬워서, 다른 사람의 풀이를 보기 전에 꼭 제 힘으로...
blog.naver.com
요 블로그의 풀이를 보게 되었다.
정말 충격을 먹었다.
이게 Knapsack 문제라고?
일단, 이 아이디어를 활용해서 문제를 풀어보다가,
요 블로그에서 구현된 Knapsack 구현방법에 흥미를 가지게 되었다.
굉장히 공간복잡도를 잘 고려한 방법이었다.
그래서 이 방법을 활용해서 쌓아두었던 Knapsack 문제들을 풀자는 마음으로 쭉쭉 풀기 시작했다.
https://www.acmicpc.net/problem/10982
10982번: 행운쿠키 제작소
데브베이커리에서는 기념일을 맞아 직원들에게 행운쿠키를 선물하기로 하였다. 회사의 간식을 담당하는 철수는 나누어줄 행운 쿠키를 준비하는 역할을 맡게 되었다. 행운쿠키를 만들기 위해서는 N개의 행운반죽을 2개의 오븐을 이용해 구워야 한다. 각각의 행운반죽은 2개의 오븐 중 1개의 오븐에서만 구워져야 하며, 어떤 오븐에서 굽는지에 따라 구워지는데 걸리는 시간이 다르다. 각각의 오븐은 독립적으로 반죽을 구울 수 있으며, 오븐에 반죽을 넣거나 빼는데 걸리는 시간은
www.acmicpc.net
요 문제는 위 블로그에서 언급했듯이 Two machines 문제와 완전히 동일하다고 봐도 된다. (testcase 구현이란 숫자 범위만 고려하면 된다.)
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.
www.acmicpc.net
https://www.acmicpc.net/problem/14728
14728번: 벼락치기
ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 같은 힌트를 시험 전에 공지해 주셨다. 내용은 아래와 같다. 여러 단원을 융합한 문제는 출제하지 않는다. 한 단원에 한 문제를 출제한다. 단, 그 단원에 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다. 이런 두가
www.acmicpc.net
12865번 문제와 14728번 문제는 그냥 Knapsack 문제이다. 그냥 Knapsack 쓰세요라고 말하는 문제이다. 그냥 풀자
https://www.acmicpc.net/problem/12920
12920번: 평범한 배낭 2
첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 걸쳐 민호의 집에 있는 물건의 정보가 주어진다. 각각의 줄은 V, C, K (1 ≤ V ≤ M, 1 ≤ C, K ≤ 10,000, 1 ≤ V * K ≤ 10,000) 으로 이루어져 있다. V는 물건의 무게, C는 물건을 가방에 넣었
www.acmicpc.net
요 문제는 얼핏 보면 "평범한 배낭1"과 동일하다고 생각할 수 있다.
근데, 생각해보면 같은 물건을 여러 개 선택할 수 있어서, 문제가 생긴다.
하지만 해봤자 문제상으로 한 물건을 K개씩, 최대 0000개 씩 쓸 수 있다. 이걸 2의 배수로 쪼갠다고 생각하면 쉽게 해결된다. 예를 들어 10개를 사용할 수 있다면 1, 2, 4, 3 으로 쪼개는 것이다. 이렇게 쪼개면 4개의 수로 10까지 모두 표현 가능하기 때문이다. (+ 맨마지막이 8이 아니라 3인 이유는 쪼갠 숫자들의 합이 주어진 10이어야 하기 때문이다.)
아무튼 오늘 AC 받은 Knapsack 문제는 이정도이다.
이제 Knapsack을 적당하게 구현하는 방법을 알았으니, 잘 써먹어보자.
Rmx
'내가 공부하려고 만들어가는 목록' 카테고리의 다른 글
| [내공만목] BOJ 트리와 쿼리 시리즈를 풀고 싶었다.(WIP) (0) | 2020.10.26 |
|---|---|
| [내공만목] 대충 어린이날에 푼 골드 문제들 정리 (0) | 2020.05.05 |
| [내공만목] Convex Hull 공부하기 (0) | 2020.05.01 |
| [내공만목] erdos-ginzburg-ziv theorem && Zero sum problem (0) | 2020.04.11 |
| [내가 공부하려고 만들어가는 목록] 목표 01 (2) | 2020.04.10 |