Beelog

www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제는 위와 같으며, 먼저 주어진 자연수보다 작거나 같은 소수를 모두 구해 배열로 저장한 뒤, low와 high 두개의 포인트를 만들어 앞에서부터 합을 구하면서 합이 n과 같아질 때 결과값을 하나 증가시키는 방식으로 문제를 해결하였습니다. 예제로 주어진 41을 기준으로 살펴보겠습니다. 41보다 작거나 같은 소수를 먼저 구해 배열로 저장합니다. 그런 다음, sum이 주어진 41보다 작은 경우 high를 한칸 뒤로 이동시키고 그 값을 sum에 추가해줍니다. 이렇게 같은 과정을 반복하다가 sum이 41과 같아진 경우, result의 값..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제는 위와 같으며, 정렬과 투 포인트를 사용하여 문제를 해결하였습니다. 먼저 주어진 용액들을 순서대로 정렬하였습니다. 그러고 난 뒤, low와 high 두 포인트를 생성하고 각각 주어진 용액 배열의 가장 앞과 뒤를 가리키도록 하였습니다. 그리고 이때 두 수의 합의 절댓값을 sum 변수에 저장하고 계산에 사용된 두 값을 result 배열에 저장하였습니다. 최종적으로 출력할 때 ..

www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제는 위와 같으며, 연속된 수들의 부분합 중에 주어지는 S 보다 큰 값을 이루는 수의 최소 개수를 구하는 문제였습니다. 처음에는 이 문제를 배열로 만들고 각 인덱스 개수만큼 수를 더해가면서 배열의 값을 뒤로 이동시키는 방식으로 풀었는데 시간 초과가 발생하였습니다...ㅠㅠ 그래서 이 문제를 low, high 두개의 인덱스 값을 포인트로 두어 두 값을 이동시키는 방식으로 해결하였습니다. 두 포인터를..

programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제는 위와 같으며, 조합을 구해서 해결할 수 있는 문제였습니다. 1. 주어진 course 배열의 숫자만큼 코스 요리의 메뉴를 구성하기 때문에, course 배열을 반복하면서 몇개의 메뉴(A)로 코스를 결정할지 정하고 orders = ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] course = [2, 3, 4] 2. 전체 주문 배열을 돌..

www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 문제는 위와 같으며, 현재 공의 크기보다 작은 공을 잡을 수 있다는 것이 중요한 조건이기 때문에 우선 공을 크기 순으로 정렬한 리스트로 저장하였습니다. 그리고 앞에서부터 공을 뽑고 그 합을 알고 있으면, 뒤에 오는 공은 항상 앞에 뽑은 공보다 크기가 크기 때문에 앞서 뽑은 모든 공의 크기에서 현재 공의 색과 같은 공들의 크기만 제거하면 잡을 수 있는 공의 크기 합을 알 수 있습니다...