UPO/8회

UPO 8회 문제는 1일차와 2일차의 구분이 없습니다. 1회, 2회와 같은 협력 문제 형태로 진행될 것입니다.

문제

'R'과 'U'만으로 이루어진 문자열 S가 있다. 문자열 S를 이용해 격자의 일부를 만들 것이다. 방식은 다음과 같다.

1. 아무 칸이나 한 칸을 선택한다.
2. 문자열의 글자들을 왼쪽부터 차례대로 살펴 보면서, 3번 과정을 반복한다.
3. 만약 글자가 'R'이라면, 마지막으로 선택한 칸 오른쪽에 있는 칸을 선택한다. 만약 글자가 'U'라면, 마지막으로 선택한 칸 위에 있는 칸을 선택한다.
4. 모든 글자를 살펴볼 때까지 3번 과정을 반복한다.

예를 들어, S="RRRR"일 때와 S="RURRURU"일 때의 격자는 아래 그림에서의 굵은 선과 같다.

문자열 S에 대한 함수 f(S)를 다음과 같이 정의하자.

• f(S)는, S를 이용해 격자를 만들 때, 격자의 맨 왼쪽 아래 꼭짓점에서 맨 오른쪽 위 꼭짓점까지 최단 거리로 이동하는 경우의 수이다.

예를 들어, f("RRRR")=6, f("RURRURU")=49이다.

우리의 목표는 f(S)=N을 만족하는 문자열 S를 찾는 것이다. 이때, S의 길이는 M 이하여야 한다. N과 M은 문제별로 주어진다. N이 같을 때, M이 작을수록 어려운 문제임에 주의하라.

1. N=10, M=10
2. N=10, M=4
3. N=34, M=6
4. N=100, M=9+1
5. N=1000, M=14+1
6. N=10000, M=20+3
7. N=100000, M=24+3
8. N=999999, M=29+3
9. N=20200101, M=36+5

edit) 문제의 난이도가 하향되었습니다. M=X+Y 꼴로 나타내어져 있는 경우, X는 실제 문자열의 최소 길이이고, 여기에 여유를 주어 X+Y까지 정답으로 인정하기로 한 경우입니다.

답 및 토론

어떤 문자열 S가 주어졌을 때 뒤에 R 혹은 U를 붙인 뒤 어떤 점화관계를 살펴볼 수 있습니다. ― Sleep (토론)이 서명을 하지 않고 의견을 썼기 때문에 Bd3076가 나중에 설명을 추가하였습니다.

• 돌아가기