문제https://www.acmicpc.net/problem/3020 풀이누적합을 활용한 풀이접근법N이 최대 200,000, H가 최대 500,000으로 들어오는 것을 조심해야 한다.단순히 O(NH)로 풀게 될 경우 시간초과가 발생하기 때문에 완전탐색 쪽으로는 생각하지 않았다. 그러면 어떻게 각 구간에 대해 효율적으로 탐색할 수 있을까? 처음에 떠올랐던 건 각 구간 별로 입력을 받을 때마다 갱신하면 되지 않을까였다.N개의 입력에서 갱신하는 방법에 대해 생각한 결과 각 구간 별로 누적합 원리를 활용해서 종유석 | 석순 각각에 대해 카운팅 해준 다음, 누적합을 구하는 방식으로 풀이했다.결과에 대해서는 i구간에 대해 종유석[i] + 석순[i]의 합이 개똥벌레가 부숴야하는 장애물의 개수이며, 최소값을 구한 후 ..

문제https://www.acmicpc.net/problem/1339 풀이자료구조를 활용한 그리디 풀이첫번째 접근법 (오답)다음과 같은 우선순위를 통해서 알파벳에 대한 값을 메겼습니다.자리수가 높은 알파벳 우선같은 자리수라면 개수에 따라서반례2ABBB----wrong : 186ans : 188해당 접근으로는 바로 뒷자리수에 나오는 알파벳에 따라 잘못된 결과가 측정될 수 있었습니다. 두번째 접근법그렇다면 위와 같은 반례에 대해서 어떻게 풀이를 해야할까요?처음에는 단순히 바로 뒤에 나오는 각각의 자리수에 대해서 알파벳의 개수를 측정하고, 비교하려 했는데요. 이렇게 될 경우 로직이 굉장히 복잡해지고 어떻게 코드를 작성해야할지 모르겠더라구요.코드를 아예 지우고 다시 생각을 해본 결과 다음과 같은 로직을 생각할 ..

문제https://www.acmicpc.net/problem/13305 풀이현재 주유소(i)와 다음 주유소(j)의 가격을 비교하여 현재 주유소가 저렴할 경우 다음 거리까지 주유.만약 다음 주유소가 저렴할 경우 현재 주유소에서 다음 주유소까지의 거리만큼만 주유.소스코드import java.io.*;import java.util.StringTokenizer;//BOJ_13305public class Main { static int cityCnt; static int[] dist, store; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new Input..

여태껏 클래스 내에서 메서드를 선언할 때 static 한정자에 대한 고민을 해본 적이 없었는데, 이번에 자바의 정석을 읽는 도중 좋은 내용을 건진 것 같아 포스팅하여 정리하고자 한다. public class Test { int x; int y; int add() { return x + y; } int add(int x, int y) { return x + y; }}class Practice { public static void main(String[] args) { Test t = new Test(); }}위와 같은 클래스가 있다고 가정하자.매개변수가 없는 add() 메서드의 경우 인스턴스 변수를..