코딩테스트

작년 BOJ 단계별 풀이를 진행할 때 백트래킹 단계에서 풀었던 BOJ 2580과 거의 똑같은 문제다.

보자마자 떠오르는 건 그리디와 정렬이었다. 약간의 시행 착오를 거친 뒤에, 수용량이 작은 가방부터 담을 수 있는 최대 가치의 보석을 담는다면 답을 얻을 수 있다는 결론을 내리고 코드를 쳤다.

BOJ 1197 최소 스패닝 트리와 거의 유사한 문제다. 최소 스패닝 트리의 간선은 N-1개라는 점을 이용해서 가장 높은 비용의 간선 하나만 더 제거해주면 마을은 2개로 분리된다.

2021 카카오 블라인드 테스트 문제다. Map자료구조와 조합을 통해서 접근한다.

글을 적기에 앞서, 필자의 방법은 효율적인 점화식 도출에 처참하게 실패하고 보편적인 풀이에 비해 코드가 매우 길어지고 지저분해졌음을 알립니다. 찾고 찾다 도저히 다른 풀이가 이해되지 않아 꼼수를 원하신다면 읽으셔도 좋습니다.