Doby's Lab

https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net Solved By: Floyd-Warshall A -> B로 가는 일방통행 도로가 있지만 다른 파티장을 경유하여 더 빠르게 갈 수 있는 경로가 있을 수 있다. 최단 경로 알고리즘을 요구한다. 그리고, 쿼리에서는 from 노드와 to노드가 매번 달라지므로 Dijkstra 같은 알고리즘을 써서는 매번 from노드로부터 Dijkstra를 돌릴 수는 없다. 그렇기 때문..

https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net Solved By: Knapsack DP Knapsack DP 까먹기 방지용 문제^^ #include #include #define pii pair using namespace std; int n, k; int cache[1001][10001]; pii subject[1001]; int main(){ cin >> n >> k; for(in..

https://www.acmicpc.net/problem/3733 3733번: Shares A group of N persons and the ACM Chief Judge share equally a number of S shares (not necessary all of them). Let x be the number of shares aquired by each person (x must be an integer). The problem is to compute the maximum value of x. Write a program that www.acmicpc.net Solved By: Python Technique 간혹 가다가 C++도 마찬가지지만 Python으로 문제를 풀 때도 EOF(End O..

https://www.acmicpc.net/problem/17128 17128번: 소가 정보섬에 올라온 이유 첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. (4 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 N마리 소들의 품질 점수 Ai가 순서대로 주어진다. (1 ≤ |Ai| ≤ 10) 셋째 줄에 www.acmicpc.net Solved By: Implementation Try 1) 실제로 모든 값을 계속 구하다가 O(NQ)로 인해 시간 초과가 났습니다. Try 2) 식을 정리해보다가 다음과 같은 규칙을 발견했습니다. 계산 식을 통해 구한 값이 다음 쿼리에 대한 값과 연관이 있습니다. 예를 들어 N의 크기가 5이고, Query에서 3을 요청한다면 3번째 원소..

https://www.acmicpc.net/problem/13268 13268번: 셔틀런 지훈이가 쓰러진 구간을 하나의 숫자로 출력한다. 시작점을 구간 0, 시작점부터 (시작점 미포함) 첫 번째 콘까지 (첫 번째 콘 포함) 구간을 1, 첫 번째 콘 (미포함) 부터 두 번째 콘까지 (포함) 구간 www.acmicpc.net Solved By: Implementation 이번 문제는 여러모로 뿌듯하네요. 구현 문제이다 보니 생각할 부분들이 많아서 풀어낸 뒤 성취감 Python으로 어려운 문제 풀어보기 성공 암튼 솔루션으로 넘어가 보겠습니다. 우선 자연수의 의미가 애매모호해서 0은 Exception으로 처리했습니다. 5m마다 콘이 있고, 20m까지 있어서 이동을 5m씩 해주는 게 좋지 않을까라는 생각을 했습니..

https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net Solved By: Knapsack DP 시간을 무게라고 두고, 배점을 가치라고 두었을 때, Knapsack DP를 돌려서 최대 이득 배점을 구해내면 됩니다. #include using namespace std; int cache[101][10001]; pair test[101]; int n, t; int main(){ cin >> n >> t; for..

https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net Solved By: Knapsack DP #include using namespace std; pair chapter[21]; int cache[21][201]; // 일 수 == 무게, 페이지 수 == 가치 int n, m; int main(){ cin >> n >> m; for(int i = 1; i > chapter[i].first >> chapter[i].s..

https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net Solved By: Knapsack DP 여전히 Knapsack DP 공부 중.. #include using namespace std; int cache[21][101]; pair human[21]; // first == 체력, second == 기쁨 int n; int main(){ cin >> n; for(int i = 1; i > human[i].first; } for(int i = 1; ..