TopCoder SRM 571 Div1

2013. 02. 20.

아 또 풀었는데 떨어졌다 ㅜㅜ 슬슬 하기싫어지는 그런느낌.

엄~~~~~청나게 쉬운 문제인데 왜이렇게 못풀었을까.. 실력이 제자리를 맴도는건가 싶다.

이걸 어떡해야할지 참..ㅜㅜ

이 기세라면 계속 풀어도 그린을 가는 신비한 상황도 무리가 아닐것 같다.

250

파일명을 숫자 순서가 아닌 사전 순서대로

(1.mp3, 10.mp3, 11.mp3, 12.mp3, 13.mp3, ..., 2.mp3, 20.mp3, 21.mp3, ..., 27.mp3)

정렬하는 mp3 플레이어가 있다.

이 mp3플레이어에 1.mp3 ~ N.mp3 까지 넣었을 때, 첫 50개 파일의 이름을 구하여라.

(1 ≤ N ≤ 1,000,000,000) 

이거 그냥... dfs를 돌려도 되고,

좀 무식하게 brute force를 써도 잘 된다 (50개만 구하면 되기에).

여기서는 우선 내가 푼 방식 (brute force)을 살펴보겠다.

일단 사전 순서를 잘 생각해보면

1, 10, 100, 1000, 10000, 100000, 100001, 100002, 100003, ..., 10001, 100010, 100011, ...

이런 식으로 진행된다는걸 알 수 있는데,

1, 10, 100, 1000, 10000, 100000 까지는 그냥 *10을 하면서 집어넣으면 된다.

그 다음이 바로 무식한 부분인데,

큰 자리부터 만드는데, 10000x 는 "10000" + (1 , ... , 9) ,

1000xx 는 "1000" + (1, ..., 99) 으로 나타낼 수 있단 것이 기본 아이디어이다.

이런 식으로 생각했으면, 일단 100000 에서 시작해서 자리수를 하나씩

줄여나가면서 위의 () 안 숫자들을 다 붙인다.

이러면 자리수를 많이 봐야하는게 아닌가? 라고 할 수도 있지만,

첫 50개만 구하면 되기때문에 () 안은 4자리까지만 만들어봐도 충분하다.

따라서 수행시간이 2초를 넘어갈 일은 없고, 예외가 발생할 일도 없고, 간단하다.

500

1000