본문 바로가기

Hub Algorithm/이분 탐색

Hub Algorithm/이분 탐색 2025. 1. 1. [BOJ] 백준 15573 : 채굴 (java) 🧪 15573 채굴난이도 : 🌟 골드 3유형 : 이분탐색https://www.acmicpc.net/problem/15573 📝 문제땅 위에 놓여있는 세로 N, 가로 M 길이의 광산에 1 × 1 광물 N × M개가 있으며, 각 광물은 고유의 강도Si, j를 가진다. 채굴기를 이용하여 이 광물들을 채굴하려고 한다. 채굴기는 공기와 맞닿아 있는 광물 하나를 골라 채굴할 수 있다. 바닥과 광물과만 맞닿아 있으면 채굴할 수 없다. 채굴기의 성능 D에 대해, 채굴기는 강도가 D 이하인 광물들만 채굴할 수 있다. 원하는 광물의 수 K 이상을 채굴할 수 있는 최소의 D를 구하여라.  입력 첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부..
Hub Algorithm/이분 탐색 2024. 11. 21. [BOJ] 백준 9998 : 블록 쌓기 (java) 🧪 9998 블록 쌓기난이도 : 🌟 골드 3유형 : 이분탐색https://www.acmicpc.net/problem/9998 📝 문제 윤형이와 동혁이가 블록 쌓기 놀이를 한다. 두 명 모두 너비 N의 블록 건물을 쌓았는데, 윤형이는 k번째 열에 Yk개의 블록을 쌓았고 동혁이는 k번째 열에 Dk개의 블록을 쌓았다. 윤형이와 동혁이는 블록을 쌓거나 빼면서 두 개의 똑같은 건물을 만들려고 한다.한편, 이 둘이 새로 만들려는 건물은 위 그림의 오른쪽 형태와 같이 팩맨 모양이 되어야 한다. 즉, 왼쪽에서 오른쪽으로 갈수록 블록의 개수가 감소하다가 증가하는 꼴이 되어야 한다. 또, 인접한 두 열의 블록의 개수는 정확히 한 개씩만 차이나야 하며, 블록의 개수가 가장 적은 열은 정중앙이여야 한다.방을 어지르지 않..
Hub Algorithm/이분 탐색 2024. 11. 11. [BOJ] 백준 1365 : 꼬인 전깃줄 (java) 🧪 1365 꼬인 전깃줄난이도 : 🌟 골드 2유형 : 이분탐색https://www.acmicpc.net/problem/1365 📝 문제공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소..
Hub Algorithm/이분 탐색 2024. 11. 1. [BOJ] 백준 1508 : 레이스 (java) 🧪 1508 레이스난이도 : 🌟 골드 2유형 : 이분탐색https://www.acmicpc.net/problem/1508 📝 문제세준이는 세준항공으로 돈을 무지막지하게 번 뒤, 레이스 대회를 개최했다. 레이스 트랙은 길이가 N인 직선이다.세준이는 심판 M명을 적절한 곳에 배치시키려고 한다. 심판은 아무 곳에나 배치시킬 수 있지 않다. 심판은 미리 정해진 K개의 곳에만 위치할 수 있다.세준이는 심판을 배치할 때, 가장 가까운 두 심판의 거리를 최대로 하려고 한다.심판을 어디에 배치시켜야 할지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같은 자연수이다. 또, K는 2보다 크거나 같고, 50보다 작거나 ..
Hub Algorithm/이분 탐색 2024. 3. 24. [소프티어] LV3 : 징검다리 (java) 🧪 LV3 징검다리 난이도 : 🌟 LV3 유형 : 이분 탐색 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 📝 문제 남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다. 돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는? 제약조건 1 ≤ N ≤ 3×103 인 정수 1 ≤ Ai ≤ 108 인 정수 입력 첫 번째 줄에 돌의 개수 N이 주어진다. 두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다. 출력 첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라. ..

티스토리툴바