26277번 - 다각형 서브태스크언어 제한함수 구현

수평, 수직 변들과 $N$개 꼭짓점들로 이루어진 다각형 $P$를 생각한다. 다각형 $P$의 변들은 끝점 에서만 만날 수 있고, 각 꼭짓점에는 정확히 두 변의 끝점이 만난다. 다각형 $P$의 변을 따라 반시계 방향으로 움직일 때, 꼭짓점에서 왼쪽 또는 오른쪽으로 회전하게 된다. 꼭짓점에서 왼쪽으로 회전한 경우에 L, 오른쪽으로 회전한 경우에 R로 표현해보자. 그러면 L과 R로 이루어진 문자열이 다각형을 표현한다. 예를 들어서, 그림 1의 다각형은 문자열

LLRLLRRLLRLLRLLRRLLR

로 표현된다. 문자열로 다각형을 표현할 때, 문자열의 시작은 항상 다각형의 가장 왼쪽 변의 위쪽 꼭짓점으로 한다. 이 문자는 항상 L임을 알 수 있다.

그림 1	그림 2

주어지는 문자열로 표현되는 다각형은 다음 조건을 만족해야한다: 임의의 수직선 $V$에 대해서, $V$는 다각형의 수평 변들의 내부(끝점을 제외한 부분)에서 많아야 $2$개의 교차점을 가진다.

다각형 $P$에 대해서, $P$를 포함하는 가장 작은 수직과 수평 변을 갖는 직사각형을 $B(P)$로 표 시하고, 이것은 $P$의 가장 왼쪽, 오른쪽, 위쪽, 아래쪽 변과 겹치는 수직, 수평선으로 결정됨을 알 수 있다 (그림 2).

문자 L과 R로 이루어진 길이 $N$의 문자열이 주어질 때, 이 문자열이 표현하는 위 조건을 만족하는 다각형 $P$를 그린다. 이 때, $P$의 각 변의 길이는 정수여야 한다. 그러면 $B(P)$의 면적이 최소가 되도록 하고 그 최솟값을 출력하는 프로그램을 작성하시오.

여러분은 관리자를 위해 다음 한 가지 함수를 구현해야만 한다.

• int polygon(string S) ; 길이 $N$인 문자열 $S$를 인자로 받는다. 여기서, 문자열 $S$의 각 문자는 L 또는 R이다. 이 함수는 $S$가 표현하는 다각형 $P$ 중에서 $B(P)$의 면적이 최소가 되는 것을 찾아서 그 면적을 return한다.

여러분은 polygon.cpp라는 이름의 정확히 하나의 파일을 제출해야만 한다. 이 파일에는 다음의 함수가 구현되어야 한다.

int polygon(string S);

이 함수는 위에서 설명한 것과 같이 동작하여야 한다. 물론, 다른 함수들을 만들어서 내부적으로 사용할 수 있다. 제출한 코드는 입출력을 수행하거나 다른 파일에 접근하여서는 안된다.

주어지는 그레이더는 다음과 같은 형식으로 입력을 읽는다:

• line $1$: $N$ ($N$ : 문자열 길이)
• line $2$: 길이 $N$의 문자열 $c_1c_2\cdots c_N$ ($c_1 = $L, $c_i = $L 또는 R, $2 \le i \le N$)

주어지는 그레이더는 함수 polygon의 return 값을 출력한다.

• 입력 문자열은 문자 L 또는 R로 구성된다.
• 입력 문자열이 표현하는 위 조건들을 만족하는 다각형은 항상 적어도 하나 존재한다.
• $4 ≤ N ≤ 800$.

• polygon_public.zip