sgc109   3년 전

세가지색의 풍선이 있고 색별 풍선의 개수가 주어질때 주어진 풍선들을 가지고

세개 모두 같은색으로 묶는것만 안될때 세개씩 묶는 최대 경우의수를 구하는문제

코포라운드 랭킹을 보니 상위 랭커분들이 다 거의 같은 코드로 아래와 같이 구현하셨던데

왜 이렇게나오는건가요? 설명해주시면 감사하겠습니다 ㅠ 

혹시 이 것과 관련된 유명한 정리가 있다거나 잘 알려진 유형이라면 알려주시면감사하겠습니다.

139   3년 전

음 설명을 잘 하는 편은 아니지만

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   3년 전

@uppo97 안녕하세요 ㅎㅎ 댓글감사합니다. 네넵 그 경우는 알겠는데 그 외에 어떻게 모두 (a+b+c)/3이되는건지 증명을못하겠어요..

139   3년 전

제가 쓰기 전에 noefferv님이 자세하게 달아주셨네요!

저도 사실 수식적으로 접근하기보단 직관적으로 다가간거라 비슷한 느낌일거에요.

너무 상세하게 설명해주셔서 제가 뭐 할 게 없을거같아요,,, 호,,

댓글을 작성하려면 로그인해야 합니다.