2019 CAL Season 1 #G 풀이

출제자 : 31기 이온조

정답 코드

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    long long N; scanf("%lld",&N);
    printf("%lld", (N/2) * (N/2 + N%2));
    return 0;
}

 

풀이법

생각해 보면, 완전탄성충돌의 횟수는 초기 상태에 서로를 바라보고 있는 두 공의 쌍의 수와 같다. 두 공이 충돌할 때 속도 교환이 일어나므로 두 공의 진행 방향이 바뀌지 않는다고 생각해도 무방하다. 즉, 두 공이 충돌하는 것과 충돌하지 않고 서로를 뚫고 지나간다고 생각해도 공들의 상대적인 위치는 바뀌지 않는다.

직관적으로 생각해 보면 왼쪽 반의 공들의 초기 진행방향을 오른쪽으로 설정하고, 오른쪽 반이 공들의 초기 진행방향을 왼쪽으로 설정하면 충돌 횟수가 최대가 될 것이라고 생각할 수 있다. 이 경우 충돌 횟수는 (N/2) * (N/2 + N%2)이다. 그리고 실제로도 이 값이 최대이다.

좀 더 엄밀한 증명은 다음과 같다.

초기 진행방향을 왼쪽으로 설정하면 L, 오른쪽으로 설정하면 R으로 표현하자. 그러면 최종적으로 LLRRRLRRLRR과 같이 공의 초기 진행 방향 배치를 길이 N의 문자열로 표시할 수 있을 것이다.

Lemma) 최적의 진행 방향 배치 중 하나는 RRR...RRRLLL...LLL과 같은 꼴이다.

Proof) 어떤 진행 방향 배치 P가 존재한다고 하자. 이 때 P에 있는 R들을 모두 왼쪽으로 보내고, L들을 모두 오른쪽으로 보내서 RRR...RRRLLL...LLL과 같은 꼴로 만들었다고 하자. 이 때 어떤 문자 하나에 대해 생각해보면, 충돌 횟수가 감소하지 않음을 알 수 있다. 즉, 이렇게 배치를 바꾸면 항상 충돌 횟수가 늘어나거나 그대로이다. 그러므로 최적의 배치 중에 하나가 반드시 LLL...LLLRRR...RRR과 같은 꼴임을 알 수 있다.

이제 최적해 중 하나가 LLL...LLLRRR...RRR과 같은 꼴임을 알았다. 이때 L의 개수를 a개, R의 개수를 b개라고 하자. a+b=N이 성립하고, 이때 a*b를 최대화하는 a와 b를 찾으면 된다. N이 짝수라고 가정하면 a=b일 때 최대이고, N이 홀수일 때도 a+1=b이거나 a=b+1일 때 a*b가 최대가 된다.