UPO/8회
UPO 8회 문제는 1일차와 2일차의 구분이 없습니다. 1회, 2회와 같은 협력 문제 형태로 진행될 것입니다.
문제[편집 | 원본 편집]
'R'과 'U'만으로 이루어진 문자열 S가 있다. 문자열 S를 이용해 격자의 일부를 만들 것이다. 방식은 다음과 같다.
- 아무 칸이나 한 칸을 선택한다.
- 문자열의 글자들을 왼쪽부터 차례대로 살펴 보면서, 3번 과정을 반복한다.
- 만약 글자가 'R'이라면, 마지막으로 선택한 칸 오른쪽에 있는 칸을 선택한다. 만약 글자가 'U'라면, 마지막으로 선택한 칸 위에 있는 칸을 선택한다.
- 모든 글자를 살펴볼 때까지 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이 작을수록 어려운 문제임에 주의하라.
- N=10, M=10 (해결)
- N=10, M=4 (해결)
- N=34, M=6 (해결)
- N=100, M=9+1 (해결)
- N=1000, M=14+1 (해결)
- N=10000, M=20+3 (해결)
- N=100000, M=24+3 (해결)
- N=999999, M=29+3 (해결)
- N=20200101, M=36+5 (해결)
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)
간단한 프로그래밍을 통해 확인하면
n=100일때 URRUUURUR가 나옵니다. 외부 링크Sleep (토론) 2020년 1월 26일 (일) 20:08 (KST)
- 맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2020년 1월 26일 (일) 19:27 (KST)
n=1000 URUURURUURUURR
n=10000 URRRURRRURRURUURURUU
n=100000 URURRURURRURRUUURRURURUR
Sleep (토론) 2020년 1월 26일 (일) 21:55 (KST) 링크에 프로그램 코드 전문이 있습니다.
- 맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2020년 1월 26일 (일) 22:55 (KST)
n=999999 URRRURUURRURURRUURURURUURURUR
n=20200101 URRRRURURURURURUURUURRURURUURRUURURU
컴퓨터가 2만5천초동안 계산했습니다. ㅡ.ㅡ Sleep (토론) 2020년 1월 27일 (월) 08:49 (KST)
- 둘 다 맞습니다. 정해 코드도 유클리드 호제법을 이용합니다. 솔직히 유클리드 호제법이라는 풀이가 이렇게 짧은 시간 안에 나올 줄은 상상도 하지 못했습니다. 참고로 제가 만든 코드는 1분 안에 이 답들을 찾았던 것으로 기억합니다. 코드를 지금 못 찾고 있는데, 찾으면 올리겠습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2020년 1월 27일 (월) 10:50 (KST)
코드
- 위와 같은 코드를 사용하면 10초 이내에 정답을 얻을 수 있습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2020년 1월 27일 (월) 10:56 (KST)