음 설명을 잘 하는 편은 아니지만
R+G+B = N이라고 가정해 둔 상태로 시작해볼게요.
i) R > 2(G+B)
G+B가 되는데, 편하게 N/3을 G+B에게, 2N/3을 R에게 배분한다고 생각해보면, (2R+G), (2R+B)와 같이 묶으면 N개를 전부 남기지 않고 묶을 수 있어요!
그럼 R > 2(G+B)니까, 위와 같이 생각을 해보면 (2R+G), (2R+B)로 묶으면 G, B는 전부 소모할 수 있고 R-2(G+B)개의 풍선이 남겠죠?
이렇게 생각해보면 어떤 한 색깔의 풍선이 2N/3을 넘어간다면, 2:1로 매칭되게 묶는게 최적이므로 저런 아웃풋을 낼거에요.
나머지경우는 (R+G+B)/3이 되는데 시간이 없어서 나중에 이어적어볼게요
sgc109 7년 전
세가지색의 풍선이 있고 색별 풍선의 개수가 주어질때 주어진 풍선들을 가지고
세개 모두 같은색으로 묶는것만 안될때 세개씩 묶는 최대 경우의수를 구하는문제
코포라운드 랭킹을 보니 상위 랭커분들이 다 거의 같은 코드로 아래와 같이 구현하셨던데
왜 이렇게나오는건가요? 설명해주시면 감사하겠습니다 ㅠ
혹시 이 것과 관련된 유명한 정리가 있다거나 잘 알려진 유형이라면 알려주시면감사하겠습니다.