Good Bye, BOJ!

BOJ의 서비스 종료 소식을 접하고 많은 생각이 들었다.

 

어떤 분야에 이렇게 열정을 쏟아서 공부해본 적이 처음이었다.

문제 하나를 풀 때마다 느껴지는 성취감 자체가 당시의 나에겐 가장 큰 즐거움이었다.

알고리즘 문제 풀이에 재미를 느끼게 해줬다는 것 외에도 많은 것을 줬던 것 같다.

 

처음 시작할 때는 스터디에 들어가서 열심히 배우는 입장이었지만, 나중에는 내가 스터디의 멘토로서 지식을 공유할 수 있었다.

같이 팀 대회에 출전하여 머리도 꽁꽁 싸매보고, 이틀 밤낮에 걸쳐가며 하나만 붙잡고 풀어도 보고, 문제가 잘 안 풀릴 때는 짜증도 내보고, 대회에 직접 문제를 출제도 해봤다. 내가 처음 냈던 문제가 처음 풀렸을 때의 기분은 아직도 잊을 수 없다.

 

여러 활동을 한 덕분에 감사하게도 그 안에서 다양한 사람들을 만나며 더 많이 배울 수 있었다.

그동안 해왔던 모든 과정이 하나하나 소중하게 기억될 것 같다.

PS의 목적으로 문제를 풀기에 BOJ는 거의 독보적인 존재였기에 앞으로의 부재가 크게 느껴질 것 같다.

---

 

 

J - Good Bye, BOJ!

02:12 AC

 

그동안 BOJ에 감사했던 마음을 담아 제출했다.

 

 

B - Good Bye, 설탕 배달!

02:23 AC

 

시뮬레이션처럼 p[i]일차 이내에 능력치를 각각 a[i], b[i], c[i] 이상으로 만들 수 있는지 확인해서 풀었다.

 

 

C - Good Bye, 토마토!

02:56 AC

 

만들 음식의 개수는 2개 이하라는 것을 관찰했다.

하나를 만들 경우는 단순 반복문으로 구할 수 있으니 건너뛰고, 2개를 만드는 경우를 어떻게 빠르게 구할까 생각해봤다.

시간 순으로 정렬해서 각 시간대별로 심사위원 A에게 받을 수 있는 최대 금액, B에게 받을 수 있는 최대 금액을 구했다.

이 값은 단조증가이기 때문에 하나의 음식을 고정시켜두면 골라야 할 음식은 가능한 시간대에서 가장 뒤의 값으로 정해진다.

이분 탐색으로 찾았다.

 

 

D - Good Bye, 최소 스패닝 트리!

03:18 AC

 

MST이면서 MBST가 아닌 경우를 구하라고 하길래 순간 흠칫했지만 그냥 NO를 출력하기로 했다.

MBST이면서 MST가 아닌 경우를 찾는 방법이 뭐가 더 있을지는 모르겠지만, MBST의 최대 코스트 이하의 간선만을 이용하여 최대 스패닝 트리를 만들어줬다.

 

 

A - Good Bye, 별 찍기!

03:25 AC

 

아름다운 별들이 찍혀있는 걸 보고 도망쳤는데, 시간 안에 더 못풀 것 같아서 돌아왔다.

A번이라 그런지 생각을 조금만 해도 풀리는 문제였다.