sgc109   1년 전

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

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

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

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

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

uppo97   1년 전

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

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

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

noeffserv   1년 전

저는 수식까지는 증명 못했지만 규칙을 찾아서 이해했네요.

우선 r,g,b 를 오름차순으로 정렬했을때 값을 각각 r,g,b라고 하면, 

r+g, b를 [1,2] or[2,1]를 이용해 묶을때, (r + g + b)/3 만큼 묶을수 있습니다.

그런데 여기서 [1,2] 와 [2,1]로 풍선들을 묶었을 때, 풍선이 많이 남게 되면 어떻게 하지? 라는 생각을 할수가 있습니다.

하지만 이때 남을수 있는 풍선의 개수는 0,1,2 이 셋 중에 하나 밖에 없습니다.

즉, r+g 가 9 이고 b가 2가 돼서 [2,1] 씩 들고가도 r+g에 5가 남는 경우는 없다는 의미입니다.

왜냐하면 우선 첫번째로 r,g,b 순으로 정렬했기 때문에

r+g<=2*b 를 만족하고 두번째로 앞서 if문에서 예외처리를 했기 때문에

 2*(r+g) >= b를 만족하게 됩니다. 그리고 세번째로 [1,2]or [2,1]로 들고 갈때와

나머지 풍선의 합이 위 두 부등식이 만족하는 모든 (r+g,b) 쌍을

만들수 있게 하기 때문입니다.  

다시 말해서, [1,2]or[2,1] 과 나머지 풍선 X,Y (X+Y <= 2)를 이용해

r+g<=2*b and 2*(r+g) >= b 를 만족하는 모든 쌍 (r+g, b)를 만들수 있기

때문입니다.

이것은 역으로 어떤 (r+g,b) 쌍이 들어와도 [1,2] or [2,1] 로 묶게 될때 답이 (r+g+b)/3을 

만족할수 있다는 의미입니다.

어떻게 만족하냐면 여기서 규칙을 이용하는데요..

r + g + b 가 3의 배수일때 항상 [1,2] or [2,1] 의 조합만으로 (r+g,b) 쌍을 만들수 있습니다.

예를 들어, (0, 0), (1,2), (2,4), (3,3), (3,6), (4,5), (4,8)....

이런 쌍들은 나머지도 필요없이 [1,2] or [2,1] 만으로 만들 수 있습니다. 

다음 (r+g+b) 가 3의 배수가 아닐때는 (r+g+b)가 3의 배수일때의 쌍에서 각각 나머지 +X or +Y 를 해주면 됩니다.

예를 들어 (3,6) 에서 +1,+0 을 해줘서 (4,6) 을 만들수 있고 +2, +0 을 해줘서 (5,6)을 만들수가 있습니다.

당연히 3의 배수일때의 쌍에서 +X or +Y 를 해주는 거기 때문에 X+Y <= 2를 만족하게 됩니다. 만약

X + Y == 3 이 되버리면 그건 이미 3의 배수이게 되므로 [1,2] or [2,1] 만으로 만들수 있게 되버리죠..


결국 r+g+b 가 3의 배수인 쌍들로 r+g+b 가 3의 배수가 아닌 모든 쌍들이 커버가 됩니다.

수식으로도 증명해보고 싶지만 조금 힘드네요.

그러니 결국 [1,2] or [2,1] 로 묶을 때, 남는 풍선의 개수는 0,1,2 셋 중에 하나고 이것은 답 (r+g+b)/3 을 가능하게 합니다.

uppo97   1년 전

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

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

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

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