태그브루트포스이분탐색 ← 오해할 수 있음특징알고리즘 문제를 적당히 접해본 상황에서 이 문제를 본다면 가장 먼저 이분탐색이 떠오르기 쉬운(이분탐색 유형으로 오해할 수 있는) 문제이다. 문제에서 최대 수익을 계산하는데 중요한 매개변수와 그 결과는$ y(L) = L에 대한 총 수익, L = 일정한 나무의 길이(매개변수) $ 이분탐색으로 문제를 해결할 수 있으려면 이러한 상황일때 L 이 증가/감소하면서 y가 한쪽 방향으로만 증가하거나 감소해야한다. 수식으로 표현하면 아래와 같다.$ ∀L1,L2∈R,L1 이분 탐색은 일반적으로 함수가 단조증가 or 단조감소할 때, 즉 정렬된 배열 내에서 특정 조건을 만족하는 임계값을 찾을 때 사용 가능하므로, 이 문제에 적용할 수 없다.또한, 자르는 나무의 최대 길이가 10,00..
알고리즘
태그문제 축소 유형특징대표적인 문제 축소 유형 이라고 할 수 있다.문제에서 내놓은 조건에 따르면 실제 시뮬레이션을 구현해야 한다고 오해할 수 있지만, 실제는 그렇지 않다.문제조건현재 책이 현재 박스에 들어가지 않으면, 3번으로 간다. 아니면 2번으로 간다.현재 책을 현재 박스에 넣는다. 다음 책을 손에 집고 1번으로 간다.현재 박스를 다른 쪽으로 치운 다음에, 테이프로 못 열게 봉인한다. 다음 박스를 앞으로 가져오고 1번으로 간다.입력으로 주어진 박스와 책의 순서를 변경하면 안된다.위의 조건을 해석해보자면 박스에 책을 넣는 작업은 책의 순서대로 작업해야 하며 현재 책이 박스에 들어가지 않으면 해당 박스는 봉인되기 때문에 큰 낭비가 발생할 우려가 있다.그러나 아래의 제한조건을 보자…제한조건문제에 주어진 방..
특징알고리즘 문제를 푸는 도구 중 하나인 Rolling up or down after divison을 확인할 수 있는 문제이다.풀이방법은 크게 두가지인데, 둘 다 익숙해지면 좋을 듯간단하게 작성하면 소수 나눗셈으로 변경한 뒤 ceil 함수를 사용하는 방법이 있고,정통적?인 방법으로는 몫과 나머지가 0보다 큰지 확인하는 방법이 있다.static void solve() throws Exception { int num = scan.nextInt(); // Math.ceil((double)num / 5) 과 같다. System.out.println(num / 5 + ((num % 5 > 0) ? 1 : 0));}
특징문제를 해결할 때 컴퓨터적 사고를 트일 수 있는 좋은 문제라고 생각한다.문제 조건에서 등장하는 환전한 금액(N)을 문제 조건 그대로 환전한 금액이 아닌 호근이가 현재 세어봐야 할 것(지폐 or 묶음) 이라고 생각하도록 해야한다.static void solve() throws Exception { int N = scan.nextInt(); int M = scan.nextInt(); int count = 0; while(N > 0){ count += N; N /= M; } System.out.println(count);}
특징흔한 최대-최소값 갱신 문제이며, Java에서 최대-최솟값을 간단하게 구하려면 Math.min() or Math.max() 메서드를 사용할 수 있다.//1. if문 사용 for(;;){ if(minValue > now){ minValue = now; }}//2. min, max 메서드 사용for(;;){ minValue = Math.min(now, minValue);}그러나 이 문제에서는 갱신된 최댓값과 해당 최댓값의 위치(인덱스)를 알아야 하므로 min, max 메서드를 사용할 수 없다.코드static void solve() throws Exception { int max = 0; int maxi = 1; int maxj = 1; for (int i = 1; i
