매일 3가지의 주제를 골라 문제를 풀어봅시다.
- 두 포인터
- 정렬
- 플로이드-와샬
두 포인터
- 문제 : 소수의 연속합
- 난이도 : Gold 3
- 해설
- 기본적인 두 포인터 문제와 같은 유형의 문제입니다.
- 다른 점이 하나 있다면 기존 문제는 부분합을 구할 배열이 주어졌지만 이 문제에서는 주어지지 않고 소수배열을 만들어서 사용해야합니다.
- 소수를 구하는 것은 에라토스테네스의 체 알고리즘을 사용하였습니다.
- 소스 코드 : https://www.acmicpc.net/source/30503075
정렬
- 문제 : 보석 도둑
- 난이도 : Gold 2
- 해설
- 보석을 기준으로 넣을 수 있는 가방을 찾는 것이 아니라 가방을 기준으로 넣을 수 있는 보석들을 찾는 것입니다.
- 가방에 넣을 수 있는 무게를 오름차순으로 정렬하여 첫번째 가방부터 넣을 수 있는 보석들을 찾고 난 뒤 해당 보석들 중에서 가장 값어치가 나가는 보석을 답에 추가하면 된다.
- 위에서 찾은 보석들은 저장해두었다가 다음 가방에서도 동일하게 적용하면 된다. 동일하게 적용하는 이유는 모든 가방이 무게순으로 정렬되있기 때문에 다음 가방에서도 이미 저장된 보석들은 담을 수 있기 때문입니다.
- 소스 코드 : https://www.acmicpc.net/source/30513777
