문제 - 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 함 - 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 함 - M명의 조카가 있고 N개의 과작 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이 구하기 - 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없음 해결방법 처음에 문제를 꼼꼼히 읽지 않아서 틀렸습니다가 계속 떴었다... 과자의 길이가 속하는 범위만 주어졌었는데 왜 그렇게 문제를 읽었는지는 모르겠지만 L1~LN까지 크기 순서대로 정렬되어 주어진다고 생각하고 문제를 풀었다. 나중에 다시 보니 해당 부분이 문제였고 정렬하는 코드를 추가해주어서 이를 해결하였다. 전체적인 문제는 이분 탐색으로 해결하였고, 막대 과자의 길이를 이분 탐색으..
문제 - 집은 0번부터 M번까지 강을 따라 번호가 매겨져 있음 - 인접한 집 사이의 거리는 모두 1 킬로미터 - 상근이는 0번 집 거주. 보트를 이용하여 사람들 운송 - 저녁까지 M번 집으로 이동해야 함 - 상근이가 M번 집으로 가는 길에 사람들을 태워주려 함 - 상근이가 모든 사람을 데려다주고 M번 집으로 가기 위해서 이동해야 하는 거리의 최솟값 구하기 해결방법 문제는 쉽게 접근할 수 있었지만 또 자료형 실수를 했다.. 그냥 맨날 int로 때려박는거 다 들킴.. 아무튼 문제로 돌아가면, 상근이가 0번에서 M번으로 이동하는 중에 사람들을 함께 운송하고 있는데, 0->M 이동하는 방향 대로 운송을 원하는 사람은 따질 필요가 없다. 어차피 가는 길에 얻어타는 느낌이니까..? 그래서 역주행을 원하는 사람들에 ..
문제 - N개의 회의를 모두 진행할 수 있는 최소 회의실 개수 구하기 - 각 회의는 시작 시간과 끝나는 시간이 주어짐 - 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없음 - 회의는 한 번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있음 - 회의의 시작 시간은 끝나는 시간보다 항상 작음 해결방법 회의 시작시간이 순서없이 입력되고 있기 때문에 회의 시간을 입력 받을 때, 시작 시간을 기준으로 정렬을 해주었다. 시작 시간을 기준으로 정렬을 하고 회의실을 하나씩 배정하면서 끝나는 시간을 기록해두었고, 끝나는 시간보다 시작 시간이 큰 회의가 있다면 해당 회의실에 다음 회의로 일정을 잡으면 되기 때문에 haveMeetingRoom 변수로 들어갈 수 있는 회의실..
문제 - 매우 큰 도화지에 자를 대고 선을 그음 - 자의 한 점에서 다른 한 점까지 그음 - 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳은 한 번 그은 곳의 차이를 구별할 수 없음 - 그려진 선(들)의 총 길이를 구하는 프로그램 작성 해결방법 주어진 점들을 x(출발점)가 작은 순으로 정렬을 해준다. (이때, x가 같다면 y가 작은 순으로 정렬할 수 있도록 했다.) 모든 점들의 리스트에서 한 선씩 받아오는데 이전에 그었던 선의 범위 안에 속하면 계산하지 않고, 범위에 속하면서 더 그을 수 있으면 더 그은 부분만을 계산해주고 아예 범위를 벗어나서 선을 그은 부분은 그 길이만큼 계산할 수 있도록 코드를 구성하였다. 처음에 범위를 제대로 특정하지 않고 이전 y값과 비교하..
문제 - 오늘부터 N+1일째 되는 날 퇴사하기 위해, 남은 N일 동안 최대한 많은 상담을 하려 함 - 각각의 상담은 상담을 완료하는데 걸리는 기간 T[i]와 상담을 했을 때 받을 수 있는 금액 P[i]로 이루어짐 - 상담을 적절히 했을 때, 얻을 수 있는 최대 수익을 구하기 해결방법 DP 배열을 만들어 퇴사 날까지 얻을 수 있는 수익을 최대로 저장하면서 계산했다. 최대값을 저장해두면서 각 날짜에 상담을 했을 때, 얻을 수 있는 수익을 구하고 저장하면서 문제를 해결했다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader..
문제 - 축구를 하기 위해 모인 사람은 총 N명 - 스타트 팀과 링크 팀으로 사람들을 나눠야 함 - 두 팀의 인원수는 같지 않아도 되지만, 한 명 이상이어야 함 - 각 사람에게 번호를 1 ~ N까지 배정하고 능력치를 조사함 - S[ij]는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치 - 팀의 능력치는 팀에 속한 모든 쌍의 능력치의 합 - 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려 함 해결방법 부분집합으로 팀을 구성할 수 있는 인원들을 뽑은 뒤, 각 팀별로 능력치를 합산하고 차이를 비교해 정답을 구할 수 있도록 구성하였다. 부분집합을 구하는 코드는 아래 포스팅을 참고하면 좋을 것 같다. [알고리즘] 부분집합(Subset) 부분집합(Subset) 개념 - 집합에 포..
문제 - 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수 구하기 - 예를 들어, S = [5, 1, 2]라면 구할 수 있는 부분 수열은, 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5) - 만들 수 없는 가장 작은 자연수는 4 해결방법 아무 것도 안 뽑는 경우부터, 전체 다 뽑는 경우까지의 조합의 경우를 다 더한 부분 집합을 이용하여 주어진 수로 만들 수 있는 수들의 조합을 구하였다.(subset 함수) 부분 집합을 구할 때, 뽑힌 수들을 모두 더하여 리스트를 만들어둔 뒤 정렬하고, 차례로 하나씩 검사하여 만들 수 없는 가장 작은 자연수를 찾을 수 있도록 하였다. (setResultCheck 함수) 코드 import java.io...