이분탐색

1. 개요 안녕하세요! 이 문제의 유형은 기하학 + 이분탐색입니다. 문제에서 주어진 닮음비를 바탕으로 하나의 식을 찾은 다음, 높이는 피타고라스로 구해야됩니다. 2. 문제 풀이2 - 1. 닮음비로 수식 찾기이렇게 변수를 결정하게되면 삼각형의 닮음비를 이용해 수식을 구해볼 수 있습니다. c : h1 = a1 : (a1 + a2)c : h2 = a2 : (a1 + a2) 위와 같은 닮은비를 이용해 수식을 계산하면 다음 아래와 같이 값을 정리할 수 있습니다.이와 같은 방법으로 a2도 구할 수 있습니다. a1 + a2를 k라고 해봅시다. k는 우리가 구하고자하는 너비가 됩니다. 따라서 두 수식을 더해봅시다.우변의 분자를 (a1+ a2)로 묶어서 정리해봅시다.이 다음 좌변, 우변에 공통으로 들어간 (a1 + a..

1. 개요 안녕하세요. 오늘 문제의 유형은 해쉬 + 이분 탐색입니다. 처음엔 해쉬만 사용해 풀이했습니다. 그런데 유형을 까보니 이분 탐색도 있었습니다. 그래서 이분 탐색으로도 풀이해 봤는데요. 로직은 똑같으나 naive하게 구현하느냐 parametric search를 사용하느냐 정도의 차이입니다. 시간 소요는 이분 탐색이 400ms 정도 빠릅니다. 2. 문제 풀이 parametric search를 결정하기 위한 조건을 세워봅시다. 이분 탐색을 사용하여 count에 값을 미리 결정합니다. 그리고 해당 count를 만족하기 위한 문자열를 뽑아줍니다. 문자열 중 중복인 값이 있다면 false를 반환하고 없다면 true를 반환하게 합니다.  중복을 확인하는 것은 unordered_set을 사용합니다. count..

1. 문제 풀이 백준에 등록된 태그에는 그리디라고 나왔지만 저는 parametric search를 사용하여 풀이하였습니다. 고기를 특정 금액만큼 사기로 이분 탐색으로 결정합니다. 고기의 가격이 특정 금액보다 작거나 같은 경우를 찾아 mx에 저장합니다. mx와 비용이 같으며 아직 수중에 돈이 남아있는 경우 해당 고기를 사기로 결정하고, mx보다 작은 고기는 무게만 추가하는 로직을 추가하여 순회합니다. 이때, 구매하거나 덤으로 받은 고기들의 무게 총합이 M 이상인지 검사하면 됩니다.2. 소요 시간 및 경과시작 시간: 12시 08분#1 제출 시간: 12시 18분4% WA오버플로우인지 검사하기로 결정#2 제출 시간: 12시 20분4% WA오버플로우가 아님, 최대 금액과 같은 고기는 별도로 구매해야 된다는 사실을..

1. 문제 풀이 문제 유형은 parametric search와 dijkstra입니다. 우선 이분 탐색으로 1번 컴퓨터에서 N번 컴퓨터를 연결하는데 최대로 사용할 수 있는 금액 cost를 결정합니다. 이후 간선의 가중치 정보를 cost에 맞추어 재가공하는데 cost보다 작거나 같다면 0으로 크다면 1로 간주하여 N번 컴퓨터까지 연결하는데 cost보다 비용이 큰 케이블의 개수가 몇 개인지 구합니다. 만약 d[n]에 저장되어 있는 값이 k보다 작거나 같다면 해당 cost로 탐색이 가능하다고 간주할 수 있습니다. 2. 소요 시간 및 경과시작 시간: 15시 16분#1 제출 시간: 16시 06분67% WA원인: N번 컴퓨터를 연결 못하는 경우를 구현하지 않음#2 제출 시간: 16시 12분67% WA#3 제출 시간:..