[WANTED] 2022 1st 쇼미더코드 후기

 

2022년 4월 2일 15:00 ~ 17:00에 원티드 주관 코딩테스트 대회인 쇼미더코드가 진행되었습니다.

 

https://www.wanted.co.kr/events/showmethecode

쇼미더코드 (Show Me The Code) : 원티드 주관 코딩테스트 대회 ('22년 1회차) | 원티드

 

---

문제 제목은 혹시 몰라서 가렸습니다.

 

작년 데브 카니발을 보니까 문제가 어려운 부분까지 출제되는줄 알았는데 작년에 비해 쉽게 낸 것 같아 보입니다.

 

A번

N의 값이 매우 작으므로 순열을 이용해 물약을 사는 순서의 모든 경우의 수를 확인하여 최솟값을 구해도 상관이 없습니다. 그래서 가격을 깎아주는 것도 인접 리스트나 인접 행렬 아무거나 사용해도 됐었네요. 저는 오랜만에 인접 행렬을 사용해보고 싶어서 인접 행렬을 사용해서 풀었습니다.

 

 

B번

모듈러 연산이 나와서 Tree DP부터 생각할 수 있지만, 이것도 N의 값과 Q의 값이 작습니다.

그래서 BFS의 시간복잡도가 O(V+E)니까 Q번 BFS를 돌려주어도 연산이 대략 2,000,000번이라서 시간내에 통과하고도 남게 됩니다.

 

 

C번

이것도 마찬가지로 모듈러 연산이 나와있어서 DP부터 생각할 수 있지만, 규칙이 매우 단순하기 때문에 누적합으로 문제를 풀 수 있었습니다. 그래서 W 개수, WH의 개수, WHE의 개수, 출력값이 되는 WHEE...의 개수를 누적합으로 구해주었네요.

이 경우엔 W, WH, WHE는 알파벳이 1개씩만 필요하니 단순 누적합으로 빠르게 구할 수 있지만, WHEE의 경우에는 WHE + E로 처음 답이 되거나, WHEE.. + E로 기존에 있던 답에 E가 추가 되는 것일 수도 있기 때문에 두 가지를 모두 고려해서 더해주어야 답이 나올 수 있었습니다.

---

4/12에 결과가 나왔습니다.