미궁게임 더라비린스
  • 미궁게임
  • 게시판
[2021-06-02] Division on string P hunter 00:36:25 P100 클리어 18명 참여 22명

문자열 비교 방법:


문자열 A와 B를 비교할 때는 다음과 같이 한다.
•A의 길이와 B의 길이가 다르다면, 길이가 더 작은 게 더 작다.
•A의 길이=B의 길이인 경우, 사전순으로 작은게 더 작다.



 






 

LCN을 제대로 이해했는지 확인을 위한 예제 4개

LCN(25, 16)=10

LCN(28, 19)=8

LCN(16, 31)=5

LCN(55, 59)=4

힌트 0) 정답은 6과 1이 아니고 답의 길이는 생각보다 길다. (1, 2, 4, 5는 580의 약수, 3은 537의 약수)

힌트 1) 537과 580에 적절한 변환을 하세요.

힌트 2) 정답은 수의 형태로 나타나며, 당연히 앞에는 0이 올 수 없고, 이것을 통해 가장 앞에 오는 숫자를 유추해낼 수 있다.


 

(+)LCN으로 구한 정답도 이진법의 형태로 변환한 이후에 합쳐주세요!

합친다: 

101 + 110 = 1011 (x)

101 + 110 = 101110 (o)


힌트) GCD에서 +는 말 그대로 붙이는게 아니에요!

 

정답과 해설 보기

BOAT

첫 번째 문제

GCD는 longest common subsequence를 뜻하는거였습니다.

문자열 A가 문자열 B를 나눈다는 것은, B에서 적절히 문자를 제거해주면 A가 된다는 뜻이었습니다.

outline -> o____ne

onrhyme -> on____e

GCD(outline, onrhyme)=one

GCD(seven, eleven) = even

 

 


두 번째 문제

적절한 변환은 이진법이었습니다.

가장 앞에 올 수 있는 숫자를 유추해낼 수 있다. -> 숫자는 0과 1밖에 존재하지 않는다.

이거는 두 숫자를 합친다에서 GCN으로 구한 답을 이진법으로 변환하라는 말이 없기 때문에 대충 유추할 수 있습니다.(ㅎㅎ)

1000011001=537
1001000100=580
11011은 위의 두 수에 포함되지 않는 최소 수이다. (문자열)
두 개를 나누지 않는 최소 수는 11011이다.
참고한 문제) https://www.acmicpc.net/problem/16742
백.준.조.아.

(예제 풀이)
25=10011
16=10000
1010은 위의 두 수에 포함되지 않는 최소 수이다.
28=11100
19=10011
1000은 위의 두 수에 포함되지 않는 최소 수이다.
16=10000
31=11111
101은 위의 두 수에 포함되지 않는 최소 수이다.
55=110111
59=111011
100은 위의 두 수에 포함되지 않는 최소 수이다.

(537과 580은 코드를 짠 뒤에 랜덤으로 숫자들을 만들어서 11011이 나올때까지 돌려서 나온 숫자입니다. 537과 580은 아무 의미도 없습니다.
마찬가지로 holavoid와 xwzyfont도 아무 의미도 없습니다.)


10001 + 11011 = 1000111011


BOAT를 모스 부호로 바꾸면 1000111011이다. (1은 작대기, 0은 점)

 

댓글

샨 2021-06-03 02:00 _
0
'문자열 비교방법' 은 어디에 쓰인건가요?
BiouX 2021-06-03 08:41 _
0
lcn에서 최소를 정의할 때 쓰였습니다.
근데 다시 생각해보니까 이진법으로 최소인 수여서 굳이 쓰지 않아도 됐을 것 같네요