Platinum/Platinum III5 BOJ 3830 : 교수님은 기다리지 않는다 문제링크: 실시간으로 x, y, z 가 입력된다. 이 말은 x 보다 y 가 z 만큼 무겁다는 뜻이다. 중간중간 쿼리 a, b 가 입력된다. 이 때 우리는 a 보다 b 가 얼마나 무거운지 출력해야 한다. 샘플은 최대 10만개, 쿼리와 무게관계도 최대 10만개 입력된다. 이 문제는 개인적으로 굉장히 좋은 문제라고 생각한다. 우선 Union-Find 와 관련있다는 것은 금방 관찰할 수 있다. x y z 가 입력이 되면, x 와 y 는 서로 무게 차이를 알아낼 수 있는 관계가 된다. 그 말은, x 와 서로 무게 차이를 알아낼 수 있는 샘플은 y 와도 서로 무게 차이를 알아낼 수 있다는 것이다. 따라서 쿼리 a, b 가 입력됐을 때, a 와 b 가 연결되지 않았으면 UNKNOWN 이 답이다. 하지만 이 문제는 단.. 2022. 8. 27. BOJ 2855 : 흥미로운 수열 문제 링크 : https://www.acmicpc.net/problem/2855 흥미로운 수열은 길이가 항상 2K 꼴의 짝수다. 앞 K 개와 뒷 K 개 수의 합이 둘 다 S 이하면 흥미로운 수열이다. 길이 N짜리 수열과 S가 주어졌을 때, 연속부분수열 중 가장 긴 흥미로운 수열의 길이를 출력하면 된다. 딱 봐도 이진탐색인데, 정당성이 없었다. A[1] ~ A[K] // A[K+1] ~ A[2K] 가 흥미로운 수열이 아니었다고 해도 A[1] ~ A[K+1] // A[K+2] ~ A[2K+2] 가 흥미로운 수열이 될 수 있기 때문이다. (A[K+1] 이 엄청 큰 수고 A[2K+1] + A[2K+2] 가 엄청 작으면 가능하다) 그러다 문득 가운데를 고정해놓으면 이진탐색의 정당성이 부여된다는 것을 깨달았다. A.. 2022. 8. 14. BOJ 2787 : 흔한 수열 문제 문제 링크 : https://www.acmicpc.net/problem/2787 1 x y v - x번째 수부터, y번째 수 중 제일 큰 값은 v 2 x y v - x번째 수부터, y번째 수 중 제일 작은 값은 v 이런 식으로 수열에 관한 정보를 주면 이들을 만족하는 수열을 찾아서 출력하면 된다. 수열의 정보에 관한 문제가 대부분 펜윅트리로 풀려서 그쪽으로 생각을 해봤는데 잘 안 됐다. 그러다가 N 제한이 200 인 것이 이상해서 생각해봤는데 이분매칭이 떠올랐다. 2 ~ 10 번째 수의 최댓값이 15 라면, 2 ~ 10 번째의 각 칸들을 1 ~ 15 와 연결해주고 매칭하면 된다. 하지만, 이 방법은 문제가 있다. 매칭은 정상적으로 되지만, 2 ~ 10 번째 수의 최댓값이 15 면 15가 무조건 존재한다는.. 2022. 8. 14. BOJ 1017 : 소수 쌍 문제 링크 : https://www.acmicpc.net/problem/1017 보는 순간 바로 이분매칭이 떠오른다. 하지만 이분매칭은 기본적으로 이분그래프에서 이루어져야 하기 때문에 한 번 막혔었다. 서로 다른 두 수의 합으로 생성된 소수는 무조건 홀수가 될 수 밖에 없다. 또한, 홀수는 무조건 (홀수 + 짝수) 로 만들어질 수 밖에 없다. 따라서, 이 문제는 홀수 / 짝수로 이분그래프를 형성하여 풀면 된다. 다만, 타 문제들과는 달리 첫 수와 매칭될 수 있는 수를 찾아야하기 때문에, 2 ~ N 번째 수와 1번째 수를 수동으로 매칭시킨 후 이분매칭을 실시하면 된다. 2022. 8. 14. BOJ 17167 : A Plus Equals B 문제 링크 : https://www.acmicpc.net/problem/17167 편법으로 파이썬을 쓴 문제... long long 범위의 두 자연수 A, B 가 주어졌을 때 A += A, A += B, B += A, B += B 의 네 연산을 적절히 써서 A == B 가 되게 만들라는 문제다. 이 때, 주의할 점은 꼭 최소 횟수일 필요가 없다는 것이다. A와 B가 같게만 되면 된다. 일반성을 잃지 않고, 마지막에 A 가 커져서 B와 같아졌다고 해보자. 그렇다면, A += A 가 무조건 마지막 연산이 되어야 한다. A += B 를 했는데 B 와 같아질 수 없기 때문. 여기서 조금만 더 나아가면, 마지막은 A += A 가 1번 이상 반복된 형태여야 함을 쉽게 알 수 있다. 즉 A 가 1번 이상 2배가 된다.. 2022. 8. 14. 이전 1 다음
