은비블로그

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net +,- 버튼만 사용해서 도달하는 경우와 버튼으로 바로 채널로 이동하여 +,- 버튼 사용하는 경우 두 가지 중 최솟값을 구하려고 했다. 가장 차이가 적은 고장난버튼이 포함되어있지 않은 채널을 구하는 방법을 고민하다가, 모든 경우의 수를 전부 탐색할 때, 입력된 수부터 탐색하여 해당 수에 고장난버튼이 있으면 ++해서 탐색, --해서 탐색 두 가지를 돌렸다. 그런데 구현을 너무 복잡하게..

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net %를 이용해서 풀려고 했는데 단순 반복문으로 가능했다. 쉽게 풀 수 있던 문제를 너무 꼬아 생각했던 것 같음. 메모리 : 14112 KB 시간 : 124 ms 코드길이 : 809 B [내 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringT..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net N의 최대가 굉장히 작아서 4중포문까지도 괜찮았기 때문에 편하게 코드를 짰다. 근데 코드가 너무 반복되는 것도 많고 복잡하고 길어지는 느낌이라 결국 찾아봄. 반복되는 부분이 많으면 따로 메소드를 짜서 사용하는 것이 편하다고 한다. 메소드 짜는 것도 피하지 말고 많이 해봐야 할 것 같음. 바꿀 수 있는 부분을 하나씩 바꾼 후에 요소가 바뀐 행과 열을 탐색 해주고 최댓값을 구한다. 변경은 한 번만 되니 바꿨던 부분은 다시 돌려줌. 가로로 변경되면 요소가 바뀐 열이 2개, 요소가 바뀐 행이 1개 세로로 변경되면 요소가 ..

전체 키를 합한 후 100을 뺀 값을 저장. 더해서 위의 값을 만족하는 두 수를 저장한 후에 제외한 7개의 수를 오름차순으로 출력. 메모리 : 14092 KB 시간 : 124 ms 코드길이 : 1183 B import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buff..

다른 분들의 풀이를 봐도 감도 못 잡다가, 그냥 해보니까 됐다(?) 처음에 또 최소경우 고려 안 해서 런타임에러 뜸 배열을 [2][N+1]로 바꾼 후 맞았다 가장 긴 증가하는 부분수열에서처럼 DP를 해당 인덱스까지의 합으로 두고 풀었음. 내가 푼 건 맞는데 뭔가 찝찝.. 머리로 푼 게 아니라 몸으로 푼 느낌.. DP문제를 더 풀어봐야겠다 1등코드 메모리 : 20324 KB 시간 : 192 ms 코드길이 : 1780 B 내 코드 메모리 : 110976 KB 시간 : 728 ms 코드길이 : 1154 B >> 1등과의 차이가 너무 크다... 1등 코드 공부 꼭 하기 [1등코드] import java.io.DataInputStream; import java.io.IOException; public class ..

입력되는 배열의 인덱스를 기준으로 앞에서는 가장 긴 오름차순 배열, 뒤에서는 거꾸로 시작하는 가장 긴 오름차순 배열을 합하면 되는 문제이다. 이때 하나가 겹치므로 -1 해줘야 함. 1등코드 메모리 : 13176 KB 시간 : 76 ms 코드길이 : 4653 B 내 코드 메모리 : 14556 KB 시간 : 152 ms 코드길이 : 1284 B [상위권 코드] class Main { public static void main(String[] args) throws Exception { int N = read(); int[] arr = new int[N], lis = new int[N], tmp = new int[N]; int k, l = 0; for (int i = 0; i < N; i++) { arr[i]..

가장 긴 증가하는 부분수열에서 살짝 변형된 문제였다. DP초기화를 같은 인덱스 위치의 수를 그대로 넣어서 해주는 것만 달랐음. 1등 코드 메모리 : 13260 KB 시간 : 88 ms 코드길이 : 1033 B 내 코드 메모리 : 14944 KB 시간 : 152 ms 코드길이 : 885 [1등 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int max; static int[] arr = new int[1001]; static int[] D = ne..

DP 테이블을 사용하는 것에 익숙해지지 않아서 그런지 엄청 헤맸다. 다른 분들의 코드를 봐도 모르겠어서 한참 헤매다가 개념부터 정리 후에 재도전 함. 그리고 부분수열에 대한 정의를 이상하게 기억하고 있었음;; 수학적인 부분도 주의해서 생각하자. LIS 중 가장 기본이라고 할 수 있는 문제니까 이번에 제대로 숙지해둬서 다행이라고 생각. 그리고 배열의 길이가 1일 때를 생각 못 해서 또 틀렸다. 항상 최솟값의 경우를 한 번 더 생각하자. 그리고 n의 크기가 작아서 이중포문을 통해 해결했지만 이때의 시간복잡도가 O(N^2)이므로 n의 크기가 조금이라도 커지면 굉장히 비효율적인 코드이다. 이분탐색을 통한 해결방법도 있으니 숙지해두자. 1등 코드 메모리 : 12924 KB 시간 : 72 ms 코드길이 : 838 ..

이진탐색을 사용하고 싶었는데 정확한 구현 방법이 기억이 안나서 찾아보고 구현함. 반복형과 재귀형 둘 다 사용해봤는데 메모리와 시간에 눈에 띄게 큰 차이는 없었다. 2등코드 메모리 : 41008 KB 시간 : 360 ms 코드길이 : 1929 B 내 코드 메모리 : 108760 KB 시간 : 1268 ms 코드길이 : 1234 B >> 상위권 코드와의 차이가 너무 큼.. [2등 코드] import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOException; public class Main { static class Reader { private final int BUFFER_SIZE = 1

어떻게 풀면 좋을지 고민하다 제한해둔 시간이 지나서 답을 찾아보았다. sort메서드의 compare 함수를 재정의 하여 내가 원하는대로 정렬할 수 있는 방법이 있었다. 1등 코드 메모리 : 18252 KB 시간 : 164 ms 코드길이 : 2755 B 내 코드 메모리 : 25700 KB 시간 : 328 ms 코드길이 : 898 B [상위 코드] - 1등과의 차이가 꽤 남 ( 21260 KB, 244 ms, 1103 B ) import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; p..