sehun   11달 전

안녕하세요!

1352 문제를 제가 파악을 잘 못 한 것인지, 검증할 데이터도 만들기 어렵고..

질문드립니다.


아래처럼 출력하면 되는게 아닌가요.ㅜㅜ


[sehuneileen study]$ ./a.out
6
ABCBCC


[sehuneileen study]$ ./a.out
10
ABCDBCCDDD


[sehuneileen study]$ ./a.out
16
ABCDDEBCCDDEEEEE


[sehuneileen study]$ ./a.out
100
ABBCCCCDDDDDDDDEEEEEEEEEEEEEEEEFFFFFGFFFFFFFFFFFFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG

[sehuneileen study]$ ./a.out
8
-1

[sehuneileen study]$

 

algospot   10달 전

먼저 문제점은 dfs() 내부의 for문 안에 'A'~str[n-1]+1 까지에서 str[n-1]+1 이 문제가 됩니다.

질문자께서 str[n-1]+1까지 한 이유는 사전순 빠를려면 다음문자가 최대한 작은게 와야하고, 'A'~그전문자까지 중 덜 완성된게 있다면 그걸쓰고 아니면 new character를 쓰게 되는데 new character를 쓰게 된다면 모두 같은 상황이니 가장 작은 걸 쓰는 것을 목표로 두고 설정한 거 같습니다.

비슷한 논리지만, 오류가 있습니다.

'A'~str[n-1]중에 가장 큰 문자가 str[n-1]이 아닐수도 있습니다. 즉, for 문들어가기전에

str[0]~str[n-1]중 가장 큰 문자열을 찾은뒤 그 문자열+1 까지 조사하면 되겠습니다.

하지만 그걸 고친다면 오답은 면할수있지만, 64~80의 분포에 대한 시간초과를 면할 순 없어서 그걸 생각 해 보시면 될거 같습니다.

sehun   8달 전

정말로, 정말로, 답변 감사드립니다!

이런 오류가 있는지도 몰랐습니다.

이제 시간초과를 해결해 봐야 겠습니다.! 



algospot   8달 전

sehun님께 도움을 줄 수 있어서 저도 기분이 좋네요~

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