mystika   7달 전

문제 주소는 https://code.google.com/codejam/contest/6254486/dashboard#s=p1 입니다.

저는 문제만 보고 recursive function을 작성했는데 인풋이 짧으면 제대로 처리는 되는데 길면(8~10 자리) timeout이 나더라고요. 당연히 recursive하게 작성했으니 그렇겠지만.. 군대 사지방에서 하는거라 시간도 없고 결국은 못 풀었습니다.


컨테스트 끝나고 나서 상위에 랭크된 유저들의 코드를 보긴 했지만 어떻게 접근해서 그런 코드를 작성했는지 궁금합니다. 혹시 이번 코드잼에 참여하셔서 prob B. 해결하신분들이 계시다면 이 문제 어떻게 접근하셔서 풀으셨는지 푸신 분들에게 여쭈어보고 싶습니다.

dtc03012   7달 전

어렵게 생각하지 않는게 중요합니다.

일단 저는 어떻게 풀었냐면

받은 문자열을 처음부터 끝까지 돌면서 앞뒤가 다를 때를 체크해줍니다 

그리고 마지막이 뭔지에 따라서 +1 해주냐 안해주냐로 했는데요

그 이유는 최소가 될기위해서는

a[0] 값이 + 이면 0~n 까지 +가 나오면 다 -를 시켜주고 -가 나오면 빠져나옵니다.

a[0]값이 -이면 0~n까지 -가 나오면 다 +를 시켜주고 +가 나오면 빠져나옵니다.

이런 루프를 다 돌아서 모든게 다 +일때 끝날때 걸린 횟수가 최소시간인데요.

그 루프를 도는 의미가 다를때 체크해준뒤 마지막이 뭔지에 따라 +1 해주냐 안해주냐하는 것과 같기에 저는 저렇게 짰습니다.

제가 글을 잘 못써서... 코드를 보면서 이해하는게 더 빠를거같네요


movie_jo   7달 전

제가 접근한 방법은


우선 위치를 생각하지 않고 +와 -만 생각해보면

한 번 뒤집을때마다 +는 -가 되고, -는 +가 됩니다.

+는 0번, 2번, 4번, ... 2n번 짝수번 뒤집을 때 +가 되고

-는 1번, 3번, 5번, ... 2n + 1번 홀수번 뒤집을 때 +가 됩니다.


그 다음은 위치를 생각해보면

왼쪽 끝부터 오른쪽의 어느 지점까지를 뒤집는데

여기서 왼쪽에 있는 것들은 오른쪽보다 항상 더 많이 뒤집히거나 같은 횟수만큼 뒤집히게 됩니다.

오른쪽이 포함이 되면서 왼쪽이 포함이 안되게 뒤집을 수 없으니까요.


이렇게 생각하면

+++++----+++--++- 를 예를 들어보겠습니다.

제일 오른쪽의 -를 +로 만들기 위해서는 최소 1번 뒤집어야 합니다.

++는 제일 오른쪽의 -를 뒤집는것이 예약이 되어 있으므로 한 번 더 뒤집어야 하고

--는 뒤에서 2번 뒤집는것이 예약되어 잇으므로, 한 번 더 뒤집어야 하고

...

이런식으로 하다보면 결국 +, -가 바뀌는 갯수마다 한 번 더 뒤집어야 한다는 결론이 나옵니다.


kyma123   7달 전

같은 기호가 연속돼 있을 경우, 이를 묶어서 하나로 생각해도 무방함은 자명합니다. ---를 한 번에 뒤집지 않고 나눠서 뒤집는 것은 언제나 비효율적이니까요. 때문에 +와 -가 몇 번이나 교대로 나왔느냐가 핵심입니다.
또, 마지막 기호가 +인 경우, 어차피 이 팬케익은 뒤집을 일이 없으므로 제외해도 무방합니다.
때문에 주어진 문자열은 +기호와 -기호가 번갈아 나오고, 마지막이 -로 끝나는 문자열로 표준화 할 수 있습니다.
길이 N인 표준화된 문자열 S를 flip하는 횟수가 M일 때, 길이 N+1인 문자열 S'를 flip하는 횟수는 몇 회 일까요? M+1회입니다. (손으로 몇 개 써 보시면 자명함을 알 수 있습니다.)
길이 1인 문자열을 flip하는 횟수는 1이기 때문에 M = N임을 알 수 있고, 때문에 문자열을 표준화해서 길이를 구하면 됩니다.

mystika   7달 전

다들 좋은 설명 감사드립니다.

더 공부하고 문제도 많이 풀어봐야겠네요 ㅎㅎ 감사합니다

댓글을 작성하려면 로그인해야 합니다.