14941번 호기심

문제 설명

이번 문제는 어떤 범위에 있는 소수가 주어졌을 경우 순서대로 3*A1 - A2 + 3*A3 ... 에 대한 수식에 대입했을 때 나오는 답을 구하는 문제입니다.

문제 풀이

나의 풀이

※이번 문제는 시간 초과, 틀렸습니다. 등 여러 이유들로 문제를 풀지 못해 먼저 문제를 푸신 분의 설명을 듣고 풀게 되었습니다ㅠ

1. 처음에는 우선 소수를 구한 뒤 주어진 범위에 있는 소수들을 수식에 각각 대입해서 문제를 푸는 식으로 했습니다. -> 시간 초과

2. 소수를 구하는 시간 복잡도를 줄이고 같은 방식으로 문제를 풀었습니다. -> 시간초과

 

문제를 읽어보니, 질문의 수는 n개이고, 문제의 이름처럼 호기심이 많은 질문자는 질문을 매우 많이 한다고 합니다...

그래서 시간 복잡도를 줄일 방법을 찾아봤지만, 도저히 생각이 나지 않아 결국 다른 분의 설명을 듣고 풀게 됐습니다...

 

실제 풀이

1. 소수 구하기 -> 리스트에 저장

2. 질문 마다 함수에 대한 답을 구하면 시간복잡도가 확 오르게 된다. -> 누적합을 구해놓는다.

3. 질문의 범위에 해당하는 소수들을 빠르게 구해야한다. -> 이분 탐색

 

소수 구하기

소수 판별 알고리즘은 에라토스테네스의 체를 선택했습니다. 이 숫자가 소수인지 판별하는 것 보다는 범위 내에 있는 소수들을 전부 구하기에 더 적합하다는 생각이 들어 에라토스테네스의 체 방식으로 소수를 구했습니다.

누적합 구하기

문제에 제시된 함수는 홀수번째 수에는 3을 곱하고 짝수번째 수에는 -1을 곱해서 더하는 식이다.

그렇다는 것은 해당 소수가 함수에 대입했을 때, 홀수 번 째일 경우와 짝수 번 째일 경우가 곱해지는 값이 달라진다는 것이다.

-> 누적합을 두개 구해야 한다. (해당 숫자가 범위내의 소수 중에서 짝수 번 째일 경우와 홀수 번 째일 경우를 나누어야 하므로)

이분 탐색

입력으로 들어온 범위 안에 있는 소수를 구해야한다. 그리고 누적합을 통해 해당 범위의 소수들을 함수에 넣었을 때의 결과값을 구하기 위해서는 범위의 처음과 끝 인덱스가 필요하다.

-> 입력으로 들어온 값을 이분 탐색으로 범위의 처음과 끝의 인덱스 값을 찾아주면 된다.

 

해결

이번 문제는 제 수준에 비해서는 어려운 문제였던 것 같습니다.

하지만, 이번 문제를 통해 시간 초과로 막혔을 때에는 어디를 좀 더 빠르게 할 수 있는지 생각을 해봐야한 다는 것을 조금 깨달은 것 같습니다.

-> 주어진 문제마다 수식에 대한 합을 구하는 것보다는 누적합을 통해!

-> 주어진 수에 대한 인덱스를 찾는 것은 이분탐색을 통해!

-> 소수 판별 알고리즘은 때에 따라 다르게 사용!

 

 

문제 링크 : https://www.acmicpc.net/problem/14941

14941번: 호기심

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/14941.py