구현3 codeforces #610 div2 B2 - K for the Price of One (구현) https://codeforces.com/contest/1282/problem/B2 빡구현 초기 돈 p와 세트로 살 수 있는 묶음단위 k, 최대 2e5개의 물품 가격이 주어질 때, 최대한 많은 물품을 구하는 경우 몇개를 사는지 구하는 문제. 한번 물건을 살 땐 단 한개를 사거나 딱 k개를 사야 한다. k개 묶음을 살 땐 가장 비싼 물품에 대해만 돈을 내면 된다. 돈 6, 묶음단위 3, 가격 2 3 4 5 7 8이 주어질 때를 생각해보면.. (초기돈은 신경쓰지 말자) 물건 1개 살 때 -> (2) 가격:2 물건 2개 살 때 -> (2),(3) 가격:5 -> 일단 신경쓰지 않는다. 더 싼 값으로 더 많이 살 수 있기 때문. 물건 3개 살 때 -> (2,3,4) 가격:4 물건 4개 살 때 -> (2),(3,4.. 2019. 12. 30. codeforces #608 div2 D - Portals (dp) https://codeforces.com/contest/1271/problem/D dp인건 파악했는데 중요한 포인트를 놓치고 식을 너무 복잡하게 짜서 틀린 문제. 성 n개, (성의 방어력 a, 성에서 영입되는 병사 b, 성에 인원 1명을 배치했을 때 받는 점수 c), 성과성을 잇는 간선 m개, 초기 병사 수 k명이 주어질 때 얻을 수 있는 최대 점수를 출력하는 문제다. pos번째 성에 인원을 1명 배치하는 경우는 최대한 늦게 하는 것이 최적이다. 예를들어 3번째 성으로 4번 5번 성에 포탈이 있다면 3번째 성에서 바로 인원을 배치하는 것보단 4번 성에서 포탈을 태워 보내는 경우가 최적이고, 그보다 5번째 성에서 3번째 성으로 인원을 배치하는 것이 최적이란 뜻이다. 위 아이디어를 자료구조로 잘 구현해 보면.. 2019. 12. 21. codeforces #597 div2 C - Constanze's Machine ( 피보나치 , 구현) https://codeforces.com/contest/1245/problem/C 단어를 입력하면 m은 nn으로, w는 uu로 바꿔서 출력하는 기계가 있다. (출력에 m이나, w가 나올 수 없다. 이경우 0 출력) 예를들어 단어에 nnn이라는 문자배열이 있다면, 가능한 입력은 nnn mn nm 총 세가지가 존재한다. 'n'이 k번 연속한 문자배열을 만들 수 있는 입력은 피보나치 수열을 이루게 된다. (왜 그런지는 모르겠다. 몇번 해보니까 규칙이 보임) 따라서 단어에서 n이 나오는 idx를 기록한 idx_n과 u가 나오는 idx를 기록한 idx_u에 대해서 적절히 연산해 주었다. #include #include #include using namespace std; const int MAX = 1e5+1; .. 2019. 11. 3. 이전 1 다음
