안드 공부를 해볼까?

1. 문제 분석 문제만 봐서는 무슨말을 하는지 모르겠다. 밑의 그림을 보자. 각 날짜마다 일정이 있고 곂치는 일정이 있으면 밑으로 추가된다. 또, 일정이 없는날이면 포함되지 않아서 따로 계산도 해줘야한다. 여기서 구분해야하는건 2가지다. 1. 일정이 중첩 2. 일정이 없는날 1번은 중첩이 될 수록 직사각형의 높이가 될 것이다. 즉, 인덱스를 이용하면 편할 것이다. 2번은 일정이 없다면 직사각형이 종료되는 시점이다. 그 전까지의 값을 구해주면 된다. 2. 구현 import java.io.*; import java.nio.Buffer; import java.util.*; public class Main { public static void main(String[] args) throws IOException..

1. 문제 분석 연속되는 수들의 합을 구하는 것이고 단순히 for문을 사용한다면 시간 초과가 나올 것이다. 이때 사용하는 것이 투포인터다. 2개의 start와 end를 통해 각 부분의 합을 구하는 것이다. 로직은 생각보다 간단하다. 만약 현재 합이 목표값 보다 작다면 end를 증가, 크거나 같다면 start를 증가를 하면 된다. 말로하는 것 보다 직접 하나씩 해보자. 테스트 케이스 1을 보자. 1 1 1 1이고 합이 2인 것을 찾아야 한다. 초기 상태다. 합인 sum이 목표값보다 작으니 end를 추가해야한다. end를 추가한 상태다. 이제 arr[start] + arr[end]는 2가 된다. 목표값이 되었으니 start를 더해주고 sum에서 arr[start]를 빼준다(arr[start]는 더해주기 전 ..

1. 문제분석 퇴사를 하기전에 일을 열심히 한다고 한다. 대단한 사람같다. 남은 N일동안 일할 때 최댓값을 구한다고 한다. 1일부터 차근차근 해보자. 1일 -> 4일부터 최댓값(3일동안 아무것도 못하므로) or 현재 일하는 가치 + 지난날 까지의 최대가치 2일 -> 8일부터 최댓값(5일동안 아무것도 못하므로) or 현재 일하는 가치 + 지난날 까지의 최대가치 자세한 방법을 찾았습니다! 2가지 기준으로 정하고 가겠습니다. 돈은 다음날 받는다. 예를 들어 1일날 일했으면 3일동안은 상담을 해야합니다. 그렇다면 1, 2, 3일은 다른 상담을 못하고 1일만의 상담을 해야합니다. 돈은 상담을 마치고 다음날에 들어오는 것으로 기준을 잡았습니다.(1일 → 4일) 내가 n일에 일했을 때, 나오는 값(점화식) 내가 1일..

1. 문제분석 동전 n가지가 존재하고 적당하게 사용해서 합이 k원이 되는 동전 개수의 최솟값을 구하는 문제다. 기존 최댓값을 구하는 문제에서 최솟값을 구하는 문제이므로 Math.min을 사용한다. 이번 문제의 핵심은 인덱스 활용이다. 인덱스를 구하고자하는 가치로 생각해서 0부터 k까지 구하면 된다. 이제 차례대로 구해보자. 테스트 케이스 1의 경우를 보겠다. 동전은 총 3개, 1, 5, 12를 가지고 있고 원하는 가치는 15원이다. 먼저 동전 1을 쓰는 경우다. 1부터 15까지 동전 개수 또한 1개 ~ 15개가 된다. 중요한 건 다음 동전, 5의 경우이다. 5가 된다면 기존 DP[5]의 경우 5가 아닌 1이 들어가는 것이 맞다(DP[IDX], IDX를 가치로 보면 된다.) 즉, 구하고자 하는 것은 DP[..

1. 문제분석 포도주를 어떻게 하면 많이 마실 수 있는지 확인하는 문제다. 연속해서 3잔은 마실 수 없고 그 중에서 가장 많이 마시는 경우를 해결해야 한다. 이 문제의 경우 백준의 계단 오르기(?)문제와 동일하다 3계단을 연속해서 올라갈 수 없고 마지막을 무조건 밟아야 하는 경우지만 이 문제는 마지막을 마시지 않아도 된다. 먼저 점화식을 세워보기 위해 테스트 케이스 1인 6 10 13 9 8 1를 보자. 첫번째 6을 마신 경우는 최대가 6이된다. -> DP[1] 두번째까지는 연속해서 마셔도 된다 최대가 6+6 = 12가 된다. -> DP[2] 세번째부턴 조건에 부합하게 마셔야 한다. 여기서 2가지를 볼 수 가 있다. -세번째 포도주를 먹는 경우 1. 첫번째까지의 최댓값 + 세번째의 값 -> DP[1] +..

1. 문제분석 문제에서 원하는 것은 스티커를 땠을 때, 때진 스티커의 최대 점수를 말한다. 처음에는 스티커를 때고 남은 것 중 최대 점수를 구하는 줄 알았지만 반대였다. 현재 테스트 케이스에서 주어지는 것으로 예를 잡아보자. 먼저 윗줄, 맨 처음 50점을 땠다고 생각하자. 위를 땠을 때 현재 까지의 최고 점수는 50이다. 다음으로 밑줄의 맨 처음, 30점을 땠다고 생각하자. 밑에만 땠을 때 까지 최고 점수는 30이다. 다음으로 윗 줄의 두번째 10점을 땐다고 생각하자. 옆의 50과 밑의 50은 때지못한다.(상하좌우가 같이 때지기 때문) 반면 밑의 줄의 30점은 때는 것이 가능하다. 그렇다면 30 + 10으로 40이지만 이미 50이 더 크므로 넘긴다. 이번에는 밑의 줄의 50점을 땐다고 생각해보자. 옆의 ..

1. 문제분석 부분 수열의 합 중에 가장 큰 수를 구하는 문제다. 증가하는 부분 수열이어야 하니 a[j] < a[i] 만약 조건에 맞을 때는 dp테이블에 저장된 값을 가져와 더해주면 된다. 2. 구현 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int dp[] = new int[N+1]; int map[] = new int[N+1]; Stri..

1. 문제분석 테스트 케이스 1을 보면 단순히 연속되는 가장 큰수를 구하는 문제 같아보인다. 하지만 테스트 케이스 2는 음수를 가지고 있지만 가장 큰 수열에 속한다. 결국 여기서 포인트는 음수, 양수 상관없이 연속적인 수의 합이 최대값인 경우를 찾는 문제다. 따라서 점화식은 dp[n] = (dp[n-1] + arr[n], arr[n])의 최대값이다. (전까지의 최댓값 + 현재값, or 지금 숫자가 최대값) 2. 구현 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..