728x90 투포인터2 [BOJ/Python] 1208. 부분수열의 합2 📌 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 📌 문제 접근 방법 시간 초과를 피하기 위해 리스트를 2개로 나누어 준다. (N의 최대값은 40으로, 나누지 않고 부분집합을 구할 경우 2^40번의 연산이 필요하다. 둘로 나눌 경우, 2^20 + 2^20번의 연산으로 줄일 수 있다.) left, right로 나눈 두 개의 부분집합에 대해서 나올 수 있는 합의 경우의 수를 구한다. 투 포인터를 활용하.. 2021. 10. 8. [BOJ/Python] 2473. 세 용액 📌 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 📌 문제 접근 방법 움직이지 않는 기준을 하나 설정하고 왼쪽, 오른쪽 인덱스를 바꿔가면서 합을 도출한다. 합이 양수라면 오른쪽 인덱스를 -1, 음수라면 왼쪽 인덱스를 +1 해줘서 0에 가깝게 만들어준다. 위의 과정을 반복하며 합이 0과 가장 가까운 인덱스 3개를 저장한다. 시간 초과 해결 1, 2의 과정으로는 자꾸 시간 초과가 나서 다음의 시도를 해보았다. 기준점(j.. 2021. 10. 7. 이전 1 다음 728x90