문제 - 매우 큰 도화지에 자를 대고 선을 그음 - 자의 한 점에서 다른 한 점까지 그음 - 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳은 한 번 그은 곳의 차이를 구별할 수 없음 - 그려진 선(들)의 총 길이를 구하는 프로그램 작성 해결방법 주어진 점들을 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...
문제 - 현재 3대 운동 중량 500 - 하루가 지날 때마다 중량이 K만큼 감소 - N개의 서로 다른 운동 키트 보유 - 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가 - 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고 이 경우의 수를 출력 해결방법 운동 키트 적용 순서를 순열을 이용하여 정하고, 적용 순서가 정해지면 하루하루 중량이 감소하고 운동을 통해 보충한 중량 증가량을 계산하여 500 이상을 유지하는지를 확인할 수 있도록 하였다. permutation 함수를 이용하여 순열을 통해 운동 키트 적용 순서를 짰고, N개(운동 키트 개수)만큼 순서를 짰다면 중량을 계산하여 조건에 따라 경우의 수를 계산하였다. 코드 import j..
문제 - 1번 방에서 출발해서 n번 방으로 도착이 목표 - 갈 수 있다면 Yes, 갈 수 없다면 No 출력 - 각 방 안에는 번호가 붙은 문이 있을 수 있고, 각 문은 해당하는 번호의 방으로 통함 - 방 안에는 레프리콘이나 트롤이 있을 수도 있음 - 레프리콘이 있는 방에 들어가면 소지금이 일정 양 이하로 떨어지지 않게 채워줌 (일정량 미만이면 그만한 양이 되도록 채워주고, 이상이면 그대로 둠) - 트롤이 있는 방에 들어가면 일정량의 통행료를 지불해야 함 해결방법 방문한 곳을 체크하면 각 방을 DFS로 탐색하여 목표하는 방까지 탐색하였다. 문제에 제시된 조건에 따라 레프리콘과 트롤을 만났을 때, 조건을 처리해주었으며 소지금이 바닥나면 해당 함수를 탈출할 수 있게 구현하였으며, 재귀적으로 탐색할 수 있도록 ..
문제 - 점 N개가 주어짐(x, y) - 해당 좌표들을 y 좌표가 증가하는 순으로 정렬 - y 좌표가 같으면 x 좌표가 증가하는 순서로 정렬 해결방법 Point class를 만들어서 좌표를 Point 배열로 저장하였다. 해당 좌표들을 정렬하기 위해 Comparator를 만들었고, 주어진 조건대로 x 좌표가 증가하는 순으로 정렬하였다. x 좌표가 같다면 y 좌표가 증가하는 순서로 정렬할 수 있도록 조건을 주었다. 이전에 풀었던 11650번 좌표 정렬하기 문제와 똑같이 해결하였다. [백준] 11650번 좌표 정렬하기(JAVA) 문제 - 점 N개가 주어짐(x, y) - 해당 좌표들을 x 좌표가 증가하는 순으로 정렬 - x 좌표가 같으면 y 좌표가 증가하는 순서로 정렬 해결방법 Point class를 만들어서 ..