원티드에서 쇼미더코드라고 대회를 개최한다길래 참여해봤다.
같은 시간에 프로그래머스에서 데브매칭도 진행한다길래 둘 중 어디를 참여할 지 고민해봤는데, 이름이 더 마음에 들어서 쇼미더코드만 지원했다.
시간이 겹친다길래 장난식으로 "컨텍스트 스위치하면서 풀면 되지"라고 얘기하고 하나만 지원했는데, 진짜로 두개 동시에 진행했어도 통과될 뻔 했다...
A. 물약구매
정확히는 기억이 안 나지만 "물약을 살 때 마다 다른 물약들의 가격이 떨어지는데, 그 때 모든 물약을 사는 최소 비용"을 구하는 문제였던 것 같다.
n이 15인가 10인가 아무튼 굉장히 작기 때문에 그냥 브루트포스로 돌아갔다. next_permutation으로 수열 돌려가면서 시뮬레이팅하면 된다.
B. 숫자 이어 붙이기
대충 수를 이어 붙혀서 만들 수 있는 제일 큰 수? 구하는 문제였다.
수가 커질 수 있기 때문에 MOD 연산이 들어가는데 괜히 longlong말고 int로 갈기다가 wa를 5번이나 맞았다..
수가 최대 $10^9$이라 전부 int를 쓰고, 적당한 곳에만 MOD를 걸어줬는데, 수를 이어 붙힐 때 10배가 되므로 $10^10$이 되서 overflow가 난다....ㅠㅠ
전부 longlong으로 갈겼음에도 불구하고 wa를 2번인가? 더 받았는데 MOD도 10배하는 부분에 걸어줘야하는데 안 걸어줘서 $10^10 * 10^9$으로 longlong도 overflow나는 바람에 ㅠㅠㅠ
괜히 욕심부리다 페널티랑 시간만 날렸다.
C. 나는 정말 휘파람을 못 불어
문자열에서 "WHEE"라는 subSequence의 개수를 모두 구하는 문제다.
W와 H는 1개씩만 판단하면 되므로 결정적이고 E는 2개를 판단해야하므로 비결정적이라 조금 고민을 했는데,
그냥 W와 H를 하나씩 잡고, 잡은 H뒤에 있는 E의 개수만 세어주면 $2^{E의 개수} - E - 1$개의 "WHEE"가 생성된다.
부분합 쓰려다가 어차피 W랑 E도 모두 인덱싱해주는게 구현이 편하므로 모든 문자를 인덱싱해주고 이분탐색만 2~3번씩 갈겨주니 AC가 떴다.
런타임에러가 3번이나 떴는데, 인덱싱해주면서 W와 H가 무조건 1번씩은 발생한다고 가정하고 로직을 짜서 거기서 RE가 떴다. 차라리 그냥 DP갈겼으면 1트에 가능했을 건데 조금 아쉽다.
문제난이도가 상상이상으로 쉬워서 빠르게 끝내고 다른 대회 참가가 가능했는데 참가신청을 안 해놓아서 조금 아쉽다. 뿐만 아니고 난이도에 비해서 try수가 너무 많아서 아쉽다. 노트도 없이 그냥 손으로만 짰는데, 앞 부분에서 한 가정을 구현하면서 까먹어 버리는 바람에 이 사단이 난 것 같다. 반성을 많이 하게 된 대회다.
