시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 506 | 127 | 113 | 28.608% |
IOI 국가는 최근 새로운 열차 노선인 IOI선을 개통했다.
IOI 열차는 한 칸짜리 단위 열차 여러 대가 연결된 모습을 하고 있으며 단위 열차의 종류는 I 또는 O이다.
안전을 위해 IOI 열차의 인접한 칸은 서로 다른 종류여야 하며, 운전석은 I칸에만 있기 때문에 열차의 양 끝 칸은 항상 I여야 한다.
예를 들어 OIOI나 IOOI와 같은 열차는 불가능하다.
열차는 각 차량의 종류를 나타낸 문자를 순서대로 이어 붙인 문자열로 나타낼 수 있으며 문자열의 길이가 곧 열차의 길이이다.
예를 들어 열차 IOIOI의 길이는 5이며 열차 I는 길이 1의 열차가 된다.
이제 IOI선의 개통 전날이다.
역사적인 첫 운행을 맡게 된 차장 승택이는 가능한 한 많은 승객을 태울 수 있도록 현재 보관 중인 단위 열차들을 이어 붙여 한 대의 긴 IOI 열차를 만들려고 한다.
현재 단위 열차 I 또는 O 여러 대가 두 차고지에 일렬로 주차되어 있다.
두 차고지 중 어디서 열차를 꺼낼 지는 자유지만, 열차를 들어서 옮길 수는 없기 때문에 차고의 입구에 가까운 열차부터 차례차례 꺼낼 수밖에 없다.
단, 열차 편성이 시작되기 전에 각 차고지에서 원하는 만큼씩 열차를 미리 외부 차고로 보내둘 수가 있다.
한 번 외부 차고로 보낸 열차칸은 열차를 편성할 때 사용할 수 없다.
또한 한 번 열차 편성이 시작된 다음엔 외부 차고로 열차를 보낼 수 없다.
위는 예제 입력에 대응하는 그림이다. 열차 편성이 시작되면 더 이상 외부 차고를 이용할 수가 없으며,
외부 차고의 열차는 열차 편성에 이용할 수가 없다.
승택이는 적절히 차량 대기소로 열차를 보낸 뒤 규칙에 맞게 열차를 이어붙여 한 대의 긴 IOI 열차를 만들 것이다.
이때 얼마나 긴 열차를 만들 수 있을까?
첫 줄에 차고 S에 저장된 열차의 수 N, 차고 T에 주차된 열차의 수 M이 주어진다. (1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000)
두 번째 줄에 차고 S에 저장된 열차들이 문자열 한 줄로 주어진다.
세 번째 줄에 차고 T에 저장된 열차들이 문자열 한 줄로 주어진다.
문자열의 첫 글자가 차고의 입구 쪽에 주차된 열차이다.
첫 줄에 가장 긴 열차의 길이를 출력한다.
열차를 만들 수 없다면 0을 출력한다.
5 5 OIOOI OOIOI
7
5 9 IIIII IIIIIIIII
1
Olympiad > Japanese Olympiad in Informatics > JOI 2012/2013 2번