BOJ 1644 소수의 연속합

1644번: 소수의 연속합

 

간단한 내용을 어렵게 설명한 문제라는 생각이 들었다.

요약하면 주어지는 자연수 N 이하의 소수를 모두 구한 뒤, 그 소수들의 구간합을 구해서 N이 되는 구간이 몇 개인지를 세는 문제이다. N이하의 소수를 구하는 것은 에라토스테네스의 체 를 이용하여 구할 수 있으니 결국 구간합을 여러 번 구하는 문제인 셈이다.

 

---

N이하의 소수를 구하는 내용은 인터넷이나 바로 전 글을 참고하여 해결했다 가정하자.

BOJ 4948 베르트랑 공준

 

그렇다면 구간합만 구하면 문제를 해결하는 셈인데, 여기에선 아래의 수열을 이용해 구간합을 구하는 방법 중 슬라이딩 윈도우 기법을 설명하고자 한다.

---

1~3번째 칸의 구간합이 4라는 것을 이미 계산했다고 가정하자.

 

이때 그다음 칸의 값을 포함한 구간합을 구할 때, 다시 1 + 1 + 2 + 3을 해야 할까?

물론 그렇게 반복문을 새로 타는 방법도 있지만 기존에 구해진 값인 4에 새로운 값인 3 하나만 추가로 더하는 것 또한 가능하다.

 

 

1~4 구간을 더한 값 7을 아는 상태에서, 2~4 구간만 더한 값을 알아낼 수는 없을까?

직접 2 ~ 4 칸을 더한 1 + 2 + 3을 계산하는 방법도 있겠지만, 이미 알려진 7에 빼고자 하는 1번째 칸의 값을 감 해주는 방법으로도 구 할 수 있을 것이다.

 

이러한 방식으로 앞뒤로 밀고 당기고, 늘이고 줄이고 하며 구간합을 구할 수 있는데 이를 이용하면 본 문제의 구간합을 간단하게 구할 수 있다.

 

 

지문의 예제 중 하나인 41을 위의 방식을 이용해 풀어보자.

 

규칙은 아래와 같다.

• 구간합을 구하여 타깃 숫자와 같은지 비교한다.
  • 구간합이 더 크다면 구간을 줄인다. (가장 앞쪽 인덱스를 잘라낸다)
  • 구간합이 더 작다면 구간을 늘린다. (뒤쪽 새로운 인덱스를 추가시킨다)
  • 구간합이 같다면 구간을 늘려/줄여 준다. (어느 쪽이든 무관)
• 구간의 가장 큰 값이 타깃 숫자를 초과하면 멈춘다.

여기서 1개

여기서 1개 추가

 

이하 생략하도록 한다.

 

 

---

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지

 

 

구간합을 구하는 문제는 세그먼트 트리나 스패닝 트리를 이용하는 방법이 일반적인데 이렇게 간단한 문제에서는 슬라이딩 윈도우가 더 적합하다고 생각되어 이렇게 구현하게 되었다.