BOJ
-
[BOJ] 2283번 - 구간 자르기Algorithm/BOJ 2022. 7. 6. 15:13
[BOJ] 2283번 - 구간 자르기 문제 푼 방식과 어떻게 풀었는지에 대해 설명하여 보겠습니다. 문제 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 문제 이해 처음 문제를 이해한 바로는 N 은 1000까지 K는 10억까지로써, K로 나누어질 수 있는 좌우 부분을 구하라는 문제로 이해하였습니다. 이에 따라 10억까지의 숫자 범위에서 메모리적으로 투포인터로 범위를 구하..
-
[BOJ] 2461번 - 대표 선수Algorithm/BOJ 2022. 7. 5. 23:43
[BOJ] 2461번 - 대표 선수 https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 문제 이해 문제는 N개의 반에 M명씩 있을 때 각각의 학생들을 선택하여 최대 최소 구간이 적게 만드는 문제 알고리즘 문제는 N개의 반에 M명씩 있을 때 각각의 학생들을 선택하여 최대 최소 구간이 적게 만드는 문제이다. 1. 접근 시에는 각 N개의 List를 Heapq로 구현 -> 맨 앞에 있는 값들을 매번 갱신하며 찾아보았지만, 시간 초과가 발생..
-
[BOJ] 20922번 - 겹치는 건 싫어Algorithm/BOJ 2022. 6. 29. 12:16
오늘 풀어본 문제는 [BOJ] 20922번 - 겹치는 건 싫어 입니다. https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 알고리즘 위 문제는 연속되는 부분 수열 중에서 특정 숫자가 K개 아래인 경우 중 제일 긴 길이를 선택하면 됩니다. N의 범위는 10만 a의 범위는 10만으로써, 메모리가 1024MB임으로 여유가 있으니 해당 범위만큼 길이를 선언하고 시작해도 무방할 것으로 보입니다. 한번만 순회하면서 가장 긴 경우의 수를 찾기 위해 투포인..