[일반] Scpc에는 뭔가 이런 문제가 자주 나오는거 같음

[익명(39.7)]

특정 알고리즘을 알고 적용해 풀어야하는 것 처럼 보이고, 실제로 그렇게 풀수 있기도 하지만, 관찰을 잘 하면 전혀 다른 알고리즘으로 더욱 간단하게 풀리는 문제. 당장 올해 1차 5번 문제도 정해 꽤 간단했음. 작년 본선 3번 문제도 SA 대신 KMP 가져다 선형적으로 풀수 있고.

[익명(118.235)]

그래

[익명(118.235)]

ㅇㅇ

[익명(61.253)]

작년 3번은 KMP도 필요 없었어 친구야

[익명(117.111)]

작년3번 뭐써야햇어?

[익명(121.181)]

ㄳㄳ 곰곰히 생각해보니 니 말이 맞아서 해보니 KMP 없어도 됬음.

[익명(121.181)]

작년 3번 내가 방금 푼 풀이는 대충 이런 느낌이었음. 우선 주어진 문자열의 첫 글자에서 시작함. 이후, 첫 글자보다 사전상 값이 같거나 작은 글자가 나올 때까지 선형탐색. 사전상 값이 작은 글자가 나왔으면, 그 글자를 제하고 시작 글자를 포함한 사이 모든 글자를 모아 만든 부분문자열은 1등 단어가 됨. 왜냐면 해당 부분문자열에서 가장 사전상 값이 작은 글자가 첫글자이고, 그와 사전상 값이 같은 글자는 그 안에 없기 때문에, 문자열을 아무리 꼬리 물고 회전시켜도 그보다 사전상 값이 같거나 작은 문자열이 나올 수 없기 때문임. 이 경우 다시 같은 과정을 반복하면 됨. 사전상 값이 같은 글자가 나왔으면, 지금까지 찾은 부분문자열이 이후 반복되어 나오는 부분을 계속 넘기고, 더 이상 반복되지 않는 부분을 찾음.

[익명(121.181)]

반복되지 않는 부분을 찾았으면, 만약 그 사전상 값이 더 큰 경우 반복되었던 부분 모두와 반복되지 않는 부분 모두를 합한 부분문자열은 1등 단어가 됨. 이 경우 다시 같은 과정을 반복하면 됨. 만약 그 사전상 값이 더 작은 경우 지금껏 반복되었던 부분 모두를 반복 된 횟수만큼 쪼개서 처리하고(예:// aaaa -> a a a a) 다시 이어 같은 과정을 반복하면 됨. 이 알고리즘은 선형적임.

[익명(1.226)]

그런게 좋은 문제지