문제 - 현재 고속도로에 휴게소가 N개 있음 - 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어짐 - 지금 휴게소를 M개 더 세우려고 함(반드시 모두 지어야 함) - 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에 휴게소를 세울 수 없음 - 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 함 - 휴게소가 없는 구간의 최댓값의 최솟값 출력 해결방법 처음에는 휴게소가 없는 구간들을 정렬하고 큰 수부터 중간에다 휴게소를 세우는 방식으로 문제를 해결하려 했으나, 나머지 테케는 잘 통과했지만 첫 테케가 막혔다.. 이분 탐색으로 문제를 해결하였는데, 휴게소 위치들을 리스트에 담아두고 휴게소 사이에 이분 탐색으로 구한 그 구간의 길이만큼씩 휴게소를 배치한다면 몇개를 배치할..
문제 - 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시함 - 이때 각 문제에 데드라인을 정함 - 동호가 받을 수 있는 최대 컵라면 수 구하기 해결방법 문제에 따른 정보를 Homework class 형태로 입력받고 데드라인을 기준으로 정렬하였고, 데드라인이 같다면 컵라면을 더 많이 주는 순으로 정렬할 수 있도록 구성하였다. 풀 문제가 정해지면 noodles 리스트에 저장해주었다. noodles 리스트는 컵라면을 더 많이 받기 위해서 정렬을 할 수 있었으면 좋겠다는 생각에 우선순위 큐를 사용하였다. input 2 100 2 100 3 500 3 500 이렇게 주어진다고 하면, (2, 100), (2, 100), (3, 500)을 선택하는 것 보다 (2, 10..
문제 - N명의 스태프는 폐활량이 다 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간이 다양함 - 각 스태프가 풍선 하나를 만드는 시간 Ai를 알고 있을 때, 풍선 M개를 만들기 위해 필요한 최소의 시간은? 해결방법 풍선 하나를 만드는 데 가장 오래 걸리는 스태프가 M개를 다 만드는 것을 처음 시작으로 잡고 이분 탐색을 진행하였다. 해당 시간이 지났을 때, 몇개의 풍선을 불었는지 계산해보면서 이분 탐색을 진행하였다. 또, 자료형으로 틀렸다 !!!!! 자료형을 잘 생각하고 문제를 해결해야 할 것 같다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Except..
문제 - 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 말한 수 중에서 중간값을 말해야 함 - 그동안 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 함 - 백준이의 동생이 말해야 하는 수를 순서대로 출력 해결방법 처음에는 리스트에 백준이가 정수를 외칠 때마다 넣어주면서 정렬을 하고, 가운데 인덱스를 구해 해당 인덱스의 숫자를 출력하는 방식으로 문제를 해결하려 했었는데 시간초과가 났다. 구글링을 통해 우선순위 큐를 두개를 써서 숫자를 계속 정렬해가면서 값을 빠르게 찾아나갈 수 있는 방법을 찾았다. 우선순위 큐 두개를 활용한 방법으로 한개씩 번갈아가면서 숫자를 넣어주면서 자동 정렬될 수 있도록 하였다. 차례로 각각에 번갈아 숫자를 넣어주었지만, 순서대로 큐에 넣었던 것이기 때문..
문제 - 보석은 M가지로 서로 다른 색상 중 한 색상 - 모든 보석을 N명의 학생들에게 나누어 주려고 함 - 보석을 받지 못하는 학생이 있어도 됨 - 학생은 항상 같은 색상의 보석만 가져감 - 한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투함 - 이런 질투심을 수치화하는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수 - 질투심이 최소가 되게 보석을 나누어 주려고 함 (질투심의 최솟값 출력) 해결방법 이분 탐색 문제를 많이 풀어보고 싶어서 선택했던 문제였기 때문에 바로 이전에 포스팅한 문제와 문제 풀이 방식은 거의 유사했다. 더보기 2023.02.26 - [Algorithm/Baekjoon] - [백준] 16401번 과자 나눠주기 (JAVA) 이분 탐색을 통해 보석을..
문제 - 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 함 - 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 함 - M명의 조카가 있고 N개의 과작 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이 구하기 - 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없음 해결방법 처음에 문제를 꼼꼼히 읽지 않아서 틀렸습니다가 계속 떴었다... 과자의 길이가 속하는 범위만 주어졌었는데 왜 그렇게 문제를 읽었는지는 모르겠지만 L1~LN까지 크기 순서대로 정렬되어 주어진다고 생각하고 문제를 풀었다. 나중에 다시 보니 해당 부분이 문제였고 정렬하는 코드를 추가해주어서 이를 해결하였다. 전체적인 문제는 이분 탐색으로 해결하였고, 막대 과자의 길이를 이분 탐색으..
문제 - 집은 0번부터 M번까지 강을 따라 번호가 매겨져 있음 - 인접한 집 사이의 거리는 모두 1 킬로미터 - 상근이는 0번 집 거주. 보트를 이용하여 사람들 운송 - 저녁까지 M번 집으로 이동해야 함 - 상근이가 M번 집으로 가는 길에 사람들을 태워주려 함 - 상근이가 모든 사람을 데려다주고 M번 집으로 가기 위해서 이동해야 하는 거리의 최솟값 구하기 해결방법 문제는 쉽게 접근할 수 있었지만 또 자료형 실수를 했다.. 그냥 맨날 int로 때려박는거 다 들킴.. 아무튼 문제로 돌아가면, 상근이가 0번에서 M번으로 이동하는 중에 사람들을 함께 운송하고 있는데, 0->M 이동하는 방향 대로 운송을 원하는 사람은 따질 필요가 없다. 어차피 가는 길에 얻어타는 느낌이니까..? 그래서 역주행을 원하는 사람들에 ..
문제 - N개의 회의를 모두 진행할 수 있는 최소 회의실 개수 구하기 - 각 회의는 시작 시간과 끝나는 시간이 주어짐 - 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없음 - 회의는 한 번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있음 - 회의의 시작 시간은 끝나는 시간보다 항상 작음 해결방법 회의 시작시간이 순서없이 입력되고 있기 때문에 회의 시간을 입력 받을 때, 시작 시간을 기준으로 정렬을 해주었다. 시작 시간을 기준으로 정렬을 하고 회의실을 하나씩 배정하면서 끝나는 시간을 기록해두었고, 끝나는 시간보다 시작 시간이 큰 회의가 있다면 해당 회의실에 다음 회의로 일정을 잡으면 되기 때문에 haveMeetingRoom 변수로 들어갈 수 있는 회의실..