AtCoder Beginner Contest 250 F - One Fourth

 

 

F - One Fourth

신발끈 공식을 사용하면 한 포인터가 움직일 때마다 계산이 가능하기 때문에

투 포인터로 둘 다 왼쪽부터 탐색하면 될꺼라고 생각했지만 구현에서 조금 문제가 있어서 틀리게 됐다.

 

중요 포인트는 2가지를 기억하면 된다.

 

1. 신발끈 공식을 사용하면 맨 마지막 곱셈은 다음 첫번째와의 곱로 넘어가게 되는데 무식하게 그대로 구현했다.

첫번째 점을 원점으로 맞춰주면 더해줄때 마지막 곱셈은 안해도 된다. 이렇게 되면 포인터가 움직일 때마다 크로스곱 한번만 하면 돼서 코딩할땐 무조건 이렇게 하는게 낫다.

 

2. 데이터가 시계반대방향으로 점이 주어지는데 마지막 점이 한바퀴 돌아서 넘어갈 수 있다는 것을 생각을 못했다.

해결책은 두가지정도 있는데 점들을 복사해서 똑같이 뒤에 붙여주거나 아니면 투 포인터에서 두번째 포인터가 1씩 증가할 때 n으로 나머지 계산해서 증가시키는 방식이 있다. 후자가 좀더 깔끔해 보인다.