백준 16977 히스토그램에서 가장 큰 직사각형과 쿼리
문제 설명(링크) www.acmicpc.net/problem/16977 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3 www.acmicpc.net 문제 요약 [l, r]영역의 직사각형만 사용하여 너비가 w인 직사각형 중 가장 넓이가 큰 것을 출력하는 문제이다. 풀이 과정 너비가 정해져 있으므로, 높이가 가장 큰 것이 넓이가 가장 크다. 또, 높이가 h인 직사각형이 존재하면 h-1인 직사각형도 존재하므로, h에 대한 이분탐색을 할 수 있다. 높이가 h인 직사각형이 존재한다는 것의 필요충분조건은..
BOJ 1017 소수 쌍
문제 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23 또는 1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23 수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 1 + 12 = 13으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 예제의 답은 4, 10이다. 입력 첫째 줄에 리스트의 크기 N이 주어진다. N은 50보다 작..