Algorithm/etc111 [파이썬] 백준 1644 : 소수의 연속합 (골드3) [파이썬] 백준 1644 : 소수의 연속합 (골드3)https://www.acmicpc.net/problem/1644풀이방향성 생각N=4백만이라, 에라스토테네스로 소수 리스트 한 번 빠르게 만든 다음 투포인터 사용연속된 소수의 합으로 다른 자연수를 만드는거라 투포인터임을 바로 알 수 있다.전체코드def prime(n): is_prime = [True]*(n+1) is_prime[:2] = [False]*2 for i in range(2,int(n**0.5)+1): if is_prime[i]: for j in range(i**2,n+1,i): is_prime[j] = False primes = [i for i, prime in.. 2024. 11. 16. [파이썬] 백준 2230 : 수 고르기(골드5) [파이썬] 백준 2230 : 수 고르기(골드5)https://www.acmicpc.net/problem/2230풀이방향성 생각입력이 10만 이상이라 $O(N^2)$로는 불가능하다.투 포인터로 제한적인 영역을 탐색하면서 $O(N)$으로 풀어주기. 전체코드import sysinput = lambda : sys.stdin.readline().rstrip()N,M = map(int,input().split())arr = [int(input()) for _ in range(N)]arr.sort()l,r = 0,0answer = float('inf')while l코멘트while 조건에서, l==r까지는 가능하다.같은 숫자에서 조건을 만족시키고, l+=1로 탈출하면 된다.양 쪽에서 포인터를 조이는지, 같은 지점에서 .. 2024. 10. 2. [파이썬] 백준 3151 : 합이 0 (골드4) [파이썬] 백준 3151 : 합이 0 (골드4)https://www.acmicpc.net/problem/3151풀이방향성 생각입력 크기가 10000이라, dict으로 val:개수 형태로 반환해서 계산하기$O(N)$으로 압축해주고, aaa, aab 에서 각 $O(N)$이라 $O(2N)$이다.abc로 0을 만드는 경우가 $O(N^2)$이라 브루트포스로 풀이 전체코드from collections import defaultdict as ddN = int(input())arr = list(map(int,input().split()))answer = [0,0,0]cnts = dd(int)for a in arr: cnts[a] += 1# a a aif cnts[0] >= 3: answer[0] += cnt.. 2024. 10. 2. [파이썬] 백준 2473 : 세 용액 (골드3) [파이썬] 백준 2473 : 세 용액 (골드3)https://www.acmicpc.net/problem/2473풀이방향성 생각정렬 이후 두 용액의 구한 후, 나머지 하나를 이분탐색으로 빠르게 찾기or 한 피벗의 값을 정해놓고 투포인터 진행정렬이 되어있는 array에서 값을 늘리거나 줄이거나만 해야하므로 피벗, 피벗+1, 맨 끝을 정한다.l = pivot+1, r=맨끝 이렇게 정한 후 용액의 ph값에 따라서 l r 움직이기.후자로 풀이 진행 전체코드import sysN = int(input())arr = list(map(int, input().split()))arr.sort()temp = sys.maxsizeanswer = []for p in range(N-2): l,r = p+1,N-1 whi.. 2024. 8. 4. 이전 1 ··· 5 6 7 8 9 10 11 ··· 28 다음