UPO/8회

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

문제

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

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

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

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

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

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

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

어떤 문자열 S가 주어졌을 때 뒤에 R 혹은 U를 붙인 뒤 어떤 점화관계를 살펴볼 수 있습니다.

최종 도달지점의 왼쪽까지 가는 경우의 수를 f1(S), 바로 아래쪽까지 가는 경우의 수를 f2(S)라고 합시다.

1. f1(SU), f2(SU) 와 f1(s),f2(s)와의 관계

f2(SU)=f(S)=f1(S)+f2(S)가 성립하며 f1(SU)=f1(S) 가 성립합니다.

2. f1(SR), f2(SR)과 f1(S), f2(S)와의 관계

그림을 그리며 확인하면

f2(SR)=f2(S) f1(SR)=f(s)=f1(S)+f2(S)

가 성립합니다.

어차피 f(s)=f1(s)+f2(s)이므로

우리는 f(s)대신 f1(s) 와 f2(s)로 2가지 성분을 가지는 벡터의 점화관계를 살펴볼 수 있습니다.

아무것도 없을 때 f1(1)=1,f2(1)=1이 성립하고

문자열 뒤에 R을 붙이는 것은 성분이 각각

1 1

0 1 인 2*2 행렬을 곱하는 것이며

문자열 뒤에 U를 붙이는 것은 성분이 각각

1 0

1 1

인 2*2 행렬을 곱하는 것과 같습니다.

Sleep (토론) 2020년 1월 24일 (금) 20:10 (KST)

좋은 접근입니다. 참고로 정해는 매우 아름답습니다. 참고하세요. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2020년 1월 24일 (금) 21:11 (KST)

n=10 일때 RRUU n=34 일때 RURURU 뭔가 피보나치 수열과 관련이 있을 듯 싶은데... Sleep (토론) 2020년 1월 25일 (토) 18:27 (KST)

1, 2, 3번 해결하셨습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2020년 1월 25일 (토) 20:03 (KST)

gcd(f1(s),f2(s))=gcd(f1(sr),f2(sr))=gcd(f1(su),f2(su)) 가 성립합니다.

전체적인 과정이 유클리드 호제법과 연관이 있을 것 같군요.

서로소인 두 수 a,b가 주어졌을 때

호제법을 하며 발생한 몫의 총합 : m이 되고

n=a+b값이 됩니다.

그러면 거꾸로 n으로 부터 a,b값을 추측한 뒤 m값을 검정하는 방법으로 나아가야 할 것 같습니다.

Sleep (토론) 2020년 1월 25일 (토) 23:39 (KST)