olrlobt

https://www.acmicpc.net/problem/2294 🔒 골드5 - #2294 동전 2 📌 테스트케이스 추가 힌트 2 15 3 5 = 3 2 15 2 1 = 8 ✍️ 풀이법 대표적인 DP 문제이고, 이 전 포스트인 동전 1 문제와 비슷하게 생각할 수 있다. DP 문제를 풀 때, 가장 먼저 고려해야 할 것은 캐싱을 통한 점화식 도출이다. 캐싱을 위해 DP 테이블을 그려보면, 가로축에 K원이 되기 위한 가치를 나열할 수 있다. 그리고 세로축에 동전을 하나씩 추가하며 문제를 해결해 보자. 먼저, 1원짜리 동전을 추가해 준다. 첫 동전 만으로는 점화식을 도출하기 어려우므로, 다음 동전으로 넘어간다. 5원짜리 동전을 추가해 주게 되면, 4원까지는 캐시에 영향을 미치지 않는다. 이후, 5원을 만들 때부..

https://www.acmicpc.net/problem/2293 🔒 골드5 - #2293 동전 1 📌 테스트케이스 추가 힌트 4 10 1 2 5 3 = 20 ✍️ 풀이법 대표적인 DP 문제이다. DP 문제를 풀 때, 가장 먼저 고려해야 할 것은 캐싱을 통한 점화식 도출이다. 캐싱을 위해 DP 테이블을 그려보면, 가로축에 K원이 되기 위한 가치를 나열할 수 있다. 그리고 세로축에 동전을 하나씩 추가하며 문제를 해결해 보자. 먼저 1원짜리 동전을 추가한다. 1원짜리 동전으로 1원을 만들던, 2원을 만들던, 3원을 만들던... 값은 모두 1이 되므로 1로 채워지게 된다. 또한, 0원을 만드는 경우도 { x } 동전을 선택하지 않는 경우 1가지로 생각할 수 있다. 다음으로 2원짜리 동전을 추가한다. 2원짜리 ..

🔒 골드5 - #12865 평범한 배낭 📌 테스트케이스 추가 힌트 5 7 6 13 4 8 3 6 5 12 2 7 = 19 ✍️ 풀이법 대표적인 DP (다이나믹 프로그래밍) 문제이다. DP 문제를 해결해야할때, 가장 먼저 고려해야 하는 것은 캐싱을 통한 점화식 생성이다. 먼저 값을 저장할 DP 테이블 만든다. 가로축은 들 수 있는 무게를 의미하며, 세로축에는 차례대로 물건의 무게와 가치를 입력한다. 먼저 첫번째 물건인, 무게 6에 가치 13의 물건이 들어가게 되면, 무게 6까지는 들 수 없으므로 DP (캐시)에 6부터 채워지게 된다. 이후, 두번째 물건인 무게 4에 가치 8의 물건이 들어가게 되면, 마찬가지로 무게 4까지는 들 수 없으므로 이 전 값인 0을 가져오게 된다. 이후, 4부터는 두 번째 물건을 ..

🔒 골드5 - #1461 도서관 📌 테스트케이스 추가 힌트 5 2 1 2 3 4 5 = 13 5 2 -45 -26 -18 -9 -4 = 89 5 3 -45 -26 -18 -9 -4 = 63 ✍️ 풀이법 해당 문제는, 문제를 이해하기와 테스트케이스가 풀어지는 과정을 구하는 것이 다소 어려웠다. 당연히 2개씩 책을 들고 간다면, 끝부터 차례로 2개씩 놓으면 된다고 생각을 했는데 답이 도출되지 않았고, 중간에 책을 놓고 가는 경우를 생각 해보니 답이 도출되었지만, 식을 세우기 어려웠다. 따라서 다시 답이 도출되는 과정을 생각해 보고 문제를 해결하였다. 내가 생각한 답이 도출되는 과정은 한 칸씩 전진하는 방법이다. 한칸씩 움직이면서, 해당 방향에 있는 모든 책들을 옮기는 방식으로 진행하면된다. 위의 테스트케이스..

https://www.acmicpc.net/problem/13164 🔒 골드5 - #13164 행복 유치원 📌 테스트케이스 추가 힌트 4 2 1 4 5 6 = 2 ✍️ 풀이법 한 조에서, 가장 큰 사람과 가장 작은 사람의 차이는 각 조원의 키의 차이의 합과 같다. 예로, 위의 예시를 보면 조는 1 / 4, 5, 6 두 개로 나누어지고 두번째 조에서 비용은 (4와 5의 차이) + (5와 6의 차이) 와 같다. 따라서 조를 나눌때는, 키 차이가 가장 큰 순으로 조를 나누어야 한다. 위 예시에서는 조를 2개로 나누었으므로, 조원 사이의 거리중 가장 큰 값을 한 개만큼 (= K-1) 지운다. 풀이방법: 1. 다음 사람과의 키 차이를 구한다. 2. 키 차이에서 큰 값부터 K-1 번째까지를 모두 제외하고 모두 더한..

🔒 골드3 - #13904 과제 📌 테스트케이스 추가 힌트 4 1 10 3 30 3 30 3 40 = 100 ✍️ 풀이법 문제는 정말 간단했다고 생각한다. 마감일부터 거꾸로 진행을 하고, 최대값부터 하나씩 빼 주는 방식으로 해결하였다. 위 테스트 케이스로 설명을 하자면, 3일에 수행 가능한 과제 = ( 30 , 30 , 40) / 40 수행 2일에 수행 가능한 과제 = ( 30, 30) / 30 수행 1일에 수행 가능한 과제 = ( 30 , 10) / 30 수행 = 100 풀이 방법: 1. 마감일 수의 최대값부터 해당 날에만 수행 가능한 과제를 수행 가능 리스트에 추가한다. 2. 수행 가능 리스트에서 최대값을 제거하고, 최종 점수에 더한다. 3. 최대값에서 1을 뺀 후, 위 과정을 반복한다. 🗝️ 풀이 ..

🔒 골드4 - #1715 카드 정렬하기 📌 테스트케이스 추가 힌트 5 10 20 10 10 40 = 190 4 10 10 10 30 = 110 ✍️ 풀이법 해당 문제는 이해했다고 생각해도 헷갈리는 경우가 많았던 것 같다. 테스트 케이스를 세우고 문제를 풀 때, 더한 값들을 한 번씩 쓰면서 다 합친 이후. 쓴 값들을 다 더해주어야 답이 나오게 된다는 점을 알고 진행하면, 이해하기 편할 것 같다. 첫 번째 케이스를 예로 들자면, 90이 나오는 과정에서 모든 카드가 합쳐지게 된다. 이 후, 파란 값 ( 더한 과정에서 나온 값) 들을 다 합치면 원하는 정답 190 이 나오게 된다. 이 문제는 토너먼트 방식을 사용하려하거나, 리그 방식을 사용하려고 하면 안 된다. 왜냐하면, 가장 작은 카드 뭉치부터 뭉쳐주어야, ..

https://www.acmicpc.net/problem/2437 🔒 골드2 - #2437 저울 📌 테스트케이스 추가 힌트 7 1 1 1 3 5 13 16 = 12 3 1 2 3 = 7 1 1 = 2 2 2 2 = 1 ✍️ 풀이법 처음에는 단순하게 추를 이용해서 1을 만들고, 2를 만들고, 3을 만들고 ... 이런 식으로 생각했었다. 하지만 추를 무게 순으로 정렬하더라도, 내가 원하는 답을 얻기 힘들다는 생각에 추가 테스트 코드를 만들어보며 좀 더 고민 해 보았다. 그 결과 내가 찾은 규칙은 다음과 같았다. 7 1 1 1 3 5 13 16 = 12 해당 테스트케이스에서 뒤에서부터 1보다 작거나 같은 값을 찾으면 세번째 (= index 2) 1에서 찾아지게 된다. 그 값의 이전 index 값들의 합은 만들..