CodeDrive

문제:

아래의 그림과 같이 높은 빌딩 사이를 따라 좁은 길이 나있다. 두 개의 사다리가 있는데 길이가 x인 사다리는 오른쪽 빌딩의 아래를 받침대로 하여 왼쪽 빌딩에 기대져 있고 길이가 y인 사다리는 왼쪽 빌딩의 아래를 받침대로 하여 오른쪽 빌딩에 기대져 있다. 그리고 두 사다리는 땅에서부터 정확하게 c인 지점에서 서로 교차한다. 그렇다면 두 빌딩은 얼마나 떨어져 있는 걸까?

입력:

첫째 줄에 차례대로 x,y,c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있다.

출력:

두 빌딩사이에 너비가 되는 수치를 출력한다. 절대/상대 오차는 10^-3까지 허용한다.

풀이방법:

 이분 탐색을 기반으로 하지만 수학적인 내용이 더 많이 들어가는 문제인 것 같다. 문제의 기본 틀은 두 빌딩 사이의 거리를 d라고 했을 때, 이를 이분 탐색으로 값을 바꾸어 간다. 임의의 d에 따라서 사다리가 교차하는 높이 h가 달라질 것이다. 따라서 이분탐색을 통해서 그 중 c와 같아지는 d를 찾도록 한다.

 임의의 d에 따라서 h를 구하는 방법은 수학의 닮음을 사용하도록 해야 한다. 사다리가 교차하는 높이를 h라 하고 선을 다음과 같이 그리면 닮음 꼴인 직각 삼각형을 얻을 수 있다.

h라는 직선이 생김에 따라 d도 d1과 d2로 나뉘게 될 것이고, h1과 h2도 다음과 같이 정의를 할 수 있을 것이다.

그러면 빗변이 x인 삼각형과 y인 삼각형에 각각 다음과 같은 닮음비를 얻을 수 있다.

 우리가 최종적으로 원하는 변수는 h이기 때문에 h=( ~ ) 와 같은 형태로 변형시켜야 할 것이다. 그러기 위해서는 d1+d2 = d임을 알고 있기 때문에 이를 활용해서 변수를 줄이도록 하자.

그러기 위해서는 일단 닮음비를 정리해서 d1과 d2에 관한 식으로 만들었다. 그리고 난 뒤에 위 두 식을 더한다면 d1과 d2를 d로 바꿀 수 있게 될 것이다.

 이제 양변을 각각 d로 나눌 수 있을 것이다. d는 두 빌딩 사이의 거리이므로 0을 초과한 거리일 것이다. 따라서 양변을 나누는 것에 문제가 없다.

 그러면 위 그림의 제일 위의 식과 같이 얻을 수 있을 것이고 좌변을 h에 대해서 묶을 수 있게 될 것이다. 좌변을 h로 묶고 난 뒤에 남은 것들을 우변으로 넘겨준다면 이를 h에 대한 식으로 만들 수 있을 것 이다. 따라서 위 그림의 두번째와 세번째 식은 그 과정을 담고 있다.

 h1과 h2는 x, y, d로 이루어진 변수이기 때문에 정확한 값을 계산할 수 있다. (d는 이분 탐색으로 정해진 값이다.) 따라서 h의 값을 구할 수 있을 것이고 이를 c와 비교하면서 c에 근접하게 d를 이분탐색으로 찾을 수 있을 것이다.

그렇게 찾은 mid값을 소숫점 셋째 자리까지 반올림해서 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/2022

문제:

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=2,000,000,000)과 M(1<=M<=10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력:

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

풀이 방법:

이분 탐색을 사용해서 풀어야 하는 문제이다. 항상 이러한 이분 탐색을 사용해서 푸는 문제들은 찍어서 최적의 값을 맞춰나간다 라는 느낌이 강하다. 따라서 이 문제도 역시 일정 값을 찍어서 근처로 구하고 그 값으로 부터 놀이기구의 번호를 찾도록 하였다.

문제링크:

https://www.acmicpc.net/problem/1561

문제:

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이 때, 적어도 M미터의 나무를 집에 가져가지 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력:

출력:

풀이 방법:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

k,n=map(int,input().split()) trees=list(map(int,input().split())) left=1 right=max(trees) answer=0 while left <= right:     count=0     mid=(left+right)//2     for tree in trees:         if tree-mid > 0:             count+=tree-mid     if count==n:         if answer < mid:             answer=mid         left=mid+1     elif count < n:         right=mid-1     else:         if answer < mid:             answer=mid         left=mid+1 print(answer)

cs

문제 링크:

문제:

입력:

출력:

풀이 방법:

문제 링크:

문제:

입력:

출력:

풀이 방법:

문제:

N개의 정수 A[1], A[2], ... , A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력:

출력:

풀이 방법:

문제:

풀이 방법: