2929 - Distribute Candies Among Children II

info

• 문제 보기: 2929 - Distribute Candies Among Children II
• 소요 시간: 💥1시간 초과
• 풀이 언어: java
• 체감 난이도: 4️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

수학 조합론

풀이 코드

info

• 메모리: 41200 KB
• 시간: 1 ms

class Solution {
    public long H3(long n) {
        return n < 0 ? 0 : (n+2)*(n+1)/2;
    }

    public long distributeCandies(int n, int limit) {
        return H3(n) - 3*H3(n-(limit+1)) + 3*H3(n-2*(limit+1)) - H3(n-3*(limit+1));
    }
}

풀이 해설

easy 문제 뜰 때 리뷰할 예정

참고로 2D DP는 TLE 터지도록 설계되어있기 때문에, 완전히 조합론 + 집합 섞은 수학문제이다.

메모

• 2D DP는 알아둘만 하지만 조합론까지는 코테 기준 오버같음