https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 저번에 푼 부분합 문제의 소수 버전. 비슷한 문제여서 금방 해결 가능했다. 아이디어 1. 소수 찾기 시간 복잡도가 빠른 에라토스테네스의 체 방법으로 소수를 찾았다. 2. 소수의 연속합 부분합 문제와 유사하게 투 포인터를 사용해서 경우의 수를 찾았다. 전체 코드 import math n = int(input()) if n == 1: print(0) exit(0) arr = [True] * (n + 1) arr[0] = False arr[1] = False for i in range(2, int(math.sqrt(n)+..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 아이디어 1. 부분합 사용 부분합에 대해 간단히 얘기해보면 0 ~ N까지의 합을 미리 구해두고 합의 차((0 ~ b까지 합) - (0 ~ a까지 합))를 통해 a부터 b까지 수의 합을 빠르게 구하는 방법이다. 그래서 for문을 사용해서 길이가 1일 때, 2일 때... N일 때 부분합의 값을 구해보며 S값이 넘는 순간 프로그램을 종료하도록 코드를 짰다. 당연하게도 시간 초과가 떴다. ..
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 아이디어 1. 조합 단순하게 리스트에 있는 값 중에서 두 개를 뽑아 계산하는 코드를 짰다. 시간 초과 발생 생각해보니까 조합이면 100000C2인데 1초로는 택도 없다. 2. 문제에 오름차순이 힌트 미리 정렬이 되어있으니까 이걸 이용하라는 의미로 해석 이분 탐색과 비슷하게 좌우에서 하나씩 좁혀가며 최솟값(0에 가까운 값)을 찾기로 결정. 코드 설명 while l < r: cur_value =..
