하루 종일 디버깅 못해 쩔쩔맸지만 양질의 문제다 차이를 mid로 둬서 이분탐색하는 건 알았지만 업데이트를 O(n^2)이 아닌 방법을 못 떠올렸다 100점이 안나오길래 다름 사람 코드 붙여넣어봤는데도 100이 안나와서 그냥 부분 성공했다 현재 위치 i를 업데이트 하면 이전 위치도 변경이 되는데 for문안에서 이중 포문 돌리는 것이 아니라 다시 반대 방향으로 for문을 돌리며 다시 업데이트 하면 된다. #define _CRT_SECURE_NO_WARNINGS #include using namespace std; #define MAX_N 100001 #define MAX_K 1000000001 int n, k; int arr[MAX_N]; int carr[MAX_N]; int ans[MAX_N]; int ma..
n개의 자성체들 사이에는 n-1개의 균형점이 무조건 존재한다고 보고 양 자성체들을 각각 s,e로 놓고 균형점(mid)의 위치를 이분탐색으로 찾아나간다. 오차범위가 무슨 말인지 못하다가 대략 이해했는데 만약 이분탐색으로 양쪽의 힘이 딱 같은 곳을 못발견한채로 s>e가 되어버리는 순간이 있다면 균형점 mid를 찾아야되는데 범위를 넘어가버린다는 것은 이분탐색으로 정확히는 모르지만 s와 e사이에 균형점이 있기는 있다는 것이다. 그럼 세부 좌표 오차일 것이므로 해당 mid를 출력해버리면 된다. s에 1e^12를 빼거나 e에서 뺐을 때 범위를 넘어가면 두 좌표 사이의 거리는 그것보다 작은 것이니까 그 사이에 무조건 있다. 그래도 mid를 출력해도 되는 이유는 10자리까지만 출력하기 때문인 것 같다. #include..
www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net package algo0501; import java.util.Scanner; public class B_1789_수들의합_Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); long s=sc.nextLong(); long left=1; long right=s; long answer=0; while(left
부분 수열1은 O(n*n)이 가능해서 dp (이중 포문)으로 많이 풀고 이 문제부터는 n이 커지므로 이분탐색*for문 O(nlogn)으로 풀 수 있는 이분탐색이 필요하다. import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { static int n; static int[] num; static ArrayList arr=new ArrayList(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); num=new int[n+1]; for (int i = 1; i
www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이분탐색 자체보다는 각 크기를 잘못 계산하는 바람에 계속 틀렸다 l=min(lesson)으로 해줬었는데 그러면 기준 크기 mid보다 각 음악의 길이가 더 클 때 문제가 된다. 따라서 l=max(lesson)으로 해줘서 최소 한 블루레이 크기에 한 음악은 들어갈 수 있도록 해줘야한다. import sys input=sys.stdin.readline from collections import deque n,m=map(in..
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 부분 수열의 길이만 구하는 문제고 실제 어떤 원소가 부분 수열을 이루고 있는지나 해당 원소의 인덱스를 구하는 문제가 아니라서 쉽게 구할 수 있다. 심지어 이 문제는 O(N*2)을 해도 풀리기 때문에 (1초= 10^9를 넘어가지 않으면 된다) 이중 반복문을 돌며 해당 원소 위치에서 가장 긴 부분 수열의 길이를 구하는 방식으로 구해도 되..
가장 작은 원소가 있는 인덱스가 피봇 위치이고 그 위치를 기준으로 값을 찾되, left, right 인덱스는 mid를 기준으로 계산한다 *mid 와 mid_pivot을 따로 계산해준다 class Solution: def search(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while leftnums[right]: left=mid+1 else: right=mid pivot=left left,right=0,len(nums)-1 while left
l, r은 시간 기준이며 모든 사람이 다 처리될 수 있는 최소 시간을 구해준다 mid(기준 시간)을 각 줄에서 처리할 수 있는 시간으로 나눠주면 전체 처리된 인원 수가 나오게 된다 1. 파이썬 def solution(n, times): l=min(times)*n//len(times) r=max(times)*n//len(times) answer=r while l=n: if answer>mid: answer=mid r=mid-1 else: l=mid+1 return answer 2. javascript 사람 수가 n보다 큰 경우도 시간을 갱신하는 조건이다. 가장 오래는 걸리는 시간을 right으로 해서 전체 시간을 각 시간으로 나눠준 것으로 사람 수를 계산한다. function solution(n, time..