누적합 (1) 썸네일형 리스트형 2021년 정올 본선 1번 헬기 착륙장 최대 반지름이 n인 원을 그리려면 페인트의 색깔과 관계없이 고정적으로 1부터 n까지의 합((n + 1)n / 2)만큼이 필요하다.따라서 dp[i][j] = 최대 반지름이 i인 원을 빨강 페인트 j통을 사용해서 색칠하는 경우의 수로 두었고 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i](가장 바깥 원을 어떤 색으로 칠할지를 나누어서) 가 나오게 된다. 이 DP를 전처리 해 두고 테스트 케이스에서 가능한 원의 크기마다 빨강 페인트의 사용 가능 범위인 max(0, 총 페인트량 - b)(파랑 페인트를 최대로 사용) 부터 a + 1(빨강 페인트를 최대로 사용) 이 나오니 이를 누적합으로 만들어서 해결하였다. 1시 57분 32초 제출, 64점#include #include #includ.. 이전 1 다음