2022 Google Kick Start Round E 참가 (22.08.20.)

1번은 간단한 직관으로 풀 수 있는 문제, n/5 + (n%5 == 0 ? 0 : 1)이었다.

2번은 binary search (upper bound)로 풀면 되는 문제였다. 다만 자기 자신이 나올 경우 예외처리를 해야 했었다.

3번은 palindrome matching 문제였다. 주어진 string에서 [0, 1~n/2]의 substring을 탐색해서 이게 palindrome이고 전체 반복된다면 이게 답이었다. n의 약수는 logn에 수렴하기 때문에 시간 내에 풀 수 있는 문제.

4번은 굉장히 복잡한 DFS 구현 문제였다. 조건이 [피자 배달 여부, 돈, 시간] 이렇게 3개였는데 상하좌우+제자리 대기 해서 각 탐색이 5^n이었고, DFS로 구현하면 안 되는 문제였다. 나중에 얘기 들어보니까 state를 변경해야 했다고 하는데 무슨 소리인지 잘 이해하지 못함. 아마 graph DP 아니었을까?

 

결론 - 3솔했다.