ㅣ

점의 개수를 N으로 지정할게

2/N(점의 개수)번째 까지는 삼각형을 그릴 수 있는 경우가 혹여나 생긴다면 삼각형을 그려주고, 그렇지 않다면 계속 점이 겹치지 않는 선분을 그려줄거야

하지만 2/N 번째 이후부터는 무조건 삼각형이 생길 수 밖에 없어

그래서 MinMax 알고리즘을 활용해서 나에게 가장 이로운 선분을 선택한다. 

이 때 가중치는 특정 선분을 그었을 때 얻을 수 있는 삼각형의 수로 결정한다. 

 

이렇게 MinMax를 할 때는 내가 어떤 선분을 그었을 때 얻을 수 있는 최대 가중치와, 이 선분을 그은 후에 상대방이 얻을 수 있는 최대 가중치를 통해 최종적으로 내가 얻을 수 있는 예상 이득을 판단하고, 그 중 나에게 가장 이득을 주는 선분을 선택할거야 

 

이 때 내가 최종적으로 얻을 수 있는 예상 이득은 내가 선분을 그었을 때 얻는 이득(가중치) A, 후에 상대방이 선분을 그었을 때 얻는 이득(가중치) B가 있다고 가정했을 때 A - B가 최대가 되는 선분을 선택하면 된다.

이렇게 계속해서 MinMax를 활용하다가 막바지에는 그리디로 변환해서 찾을거야

다만 어떤 부분에서 그리디 알고리즘을 사용할지는 모르겠어