0과 1의 쉼터

문제https://www.acmicpc.net/problem/3151풀이N개의 수 중에서 3개의 숫자 합이 0인 경우의 수를 찾으면 된다.N은 최대 10,000으로 완전 탐색을 하면 시간 초과가 발생한다.N^2 탐색으로 두 수를 고른 후, 이분 탐색으로 나머지 수를 찾으면 된다.두 수를 0부터 차례대로 완전 탐색을 하기 때문에 이분 탐색의 범위는 ( b + 1 ) ~ ( N - 1 ) 가 된다.이 때, 두 수 a, b에 대해 c가 1개가 아닐 수 있다.upper - lower로 동일한 c의 개수를 세주자.소스코드보기ttps://www.acmicpc.net/problem/3151 풀이N개의 수 중에서 3개의 숫자 합이 0인 경우의 수를 찾으면 된다.N은 최대 10,000으로 완전 탐색을 하면 시간 초과가 ..

문제https://www.acmicpc.net/problem/1477 풀이구간 1 ~ (L - 1)에 N개의 휴게소가 위치 A[i]에 존재하고, M개의 휴게소를 추가로 지었을 때, 휴게소가 없는 구간의 길이의 최댓값이 최소가 되도록 해야 한다.문제의 설명에서 알 수 있듯.M개의 휴게소를 전부 설치 가능한 경우에 대해휴게소가 없는 구간의 길이의 최댓값이 최소가 되어야 한다.휴게소가 없는 구간의 길이를 탐색 범위로 잡고, 이분 탐색을 하면 된다.배열 A의 앞 뒤에 경계 값을 붙여주어 계산을 쉽게 해보자.import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException..

문제집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가..

문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,0..

풀이 Mobius function와 Mertens function로 풀이했다. 편의상 "제곱ㄴㄴ수"는 SFI(Square Free Integer, 제곱 인수가 없는 정수)라고 부르겠다. Mobius function Mobius function은 다음의 조건에 따라 값을 반환하는 함수다. 제곱 인수가 없을 때, 소인수의 개수가 홀수이면 1 제곱 인수가 없을 때, 소인수의 개수가 홀수이면 -1 제곱 인수가 있는 정수이면 0 Mertens function Mertens function는 Mobius function의 부분합으로, 입력받은 수 까지 존재하는 SFI의 개수를 알 수 있다. K의 최댓값 즉, 1,000,000,000번째 SFI를 구하기 위해서는 Mobius function의 반환값들을 얼마나 저장해..