Categories(74)
-
2020 부산코딩경진대회 후기 / 풀이
문제 난이도는 솔브드 기준으로 1,2,3,4번 순서대로 브론즈 / 실버 / 골드 / 플레로 잘 배분된 것 같았습니다. 1번은 정사각형의 변 길이를 2 ~ $ min(N, M) $ 잡고 삼중 for 돌리면 됩니다. 시간 복잡도는 $ O(N^3) $ 가 됩니다. 2번은 투포인터 또는 분할 정복을 사용하면 됩니다. 비슷한 문제: https://www.acmicpc.net/problem/2003 3번은 $ M $번째 쓰레기가 어디서 태워지는지 알아야하는데, 대부분 최소 공배수로 접근한 것 같습나다. 그리고 대부분이 못 푼 것 같습니다. TMI로 최소공배수를 사용한 접근 방법은 잘 모르겠으나 최소 공배수로 하면 소수(prime number)로 구성된 저격 테케를 만들면, 최소 공배수의 범위가 $ unsig..
2020.09.27 -
백준 5550번 (JOI 2011년 2번), 헌책방 풀이
문제 백준 5550번 풀이 전형적인 DP (누적합+그리디) 문제로 볼 수 있습니다. "dp[i] = i권을 선택했을 때 만들 수 있는 최대 가격" 으로 점화식을 세워줍시다. 모든 장르에 대해서 i번째 책까지 골랐을 때, 해당 장르의 j개의 책을 추가로 고르는 경우로 DP table을 채워주면 됩니다. 시간복잡도는 $ O(GN^2) $이 되는데, N이 1000이고 G가 10이므로 G는 무시할만한 수준입니다. 따라서, DP의 시간복잡도는 $ O(N^2) $이 됩니다. DP의 조건이 좀 까다로워 구현하는데 고생했던 것 같습니다. 소스코드 #include using namespace std; int dp[2001]; vector book[11], sum[11]; int main() { cin.tie(0)->sy..
2020.09.27