SH

https://www.acmicpc.net/problem/25970 완전 탐색을 해야함은 자명하다. Java로 생각한 방법 중 최고 복잡도가 나오는 (부분문자열 기반, 출력 최적화x)로 풀었는데 통과되었다. 아마 "특정 언어에서 쉬운 문제"가 아닌가 싶다. 정해(문제 분류)는 비트마스킹을 활용한 풀이다. (판단데이터 B (B.length  난이도 기여에 가면 좀 더 어려운 알고리즘을 적용할 수 있다고 써있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Main { public static void main(String[] args) throws IOException { ..

https://www.acmicpc.net/problem/26091 입력을 오름차순 정렬한다. l = 현재 최소값 포인터, r = 현재 최대값 포인터로 정의한다. l+r >= M 이라면, ans++하고 다음 비교 (l++, r--) 로 넘어간다. l+r  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffere..

https://www.acmicpc.net/problem/2698 배열크기 & 한번의 탐색 복잡도 = 100(N) * 2(0 or 1) * 100(K) = 2만전체 복잡도 = 1000(TC) * 2만 = 2천만 dp[n][2][k] = n번째 자리에 0 or 1로 도달했을 때 인접 비트가 k인 경우의 수 n번째 자리가 0이면[n-1번째 자리가 0], [n-1번째 자리가 1]인 경우에서 k가 변하지 않는다. n번째 자리가 1이면[n-1번째 자리가 0]인 경우 k가 변하지 않는다.[n-1번째 자리가 1]인 경우 k가 1 증가한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java..

BOJ Linkhttps://www.acmicpc.net/problem/18869   풀이 과정1. 아래 조건을 만족해야 한다.Ai  → Bi Ai = Aj → Bi = BjAi > Aj → Bi > Bj=> 우선, 배열 A와 B를 value에 따라 정렬 했을 때, idx 순서가 같으면 된다. 2. 위 로직만 적용했을 때의 반례A = [1, 1, 1]B = [1, 1, 2]  오름차순 정렬을 했을 때, 둘 다 idx는 [0, 1, 2] 이다.그러나, A1 = 1, A2 = 1, B1 = 1, B2 = 2 이기 때문에 A1 = A2B1 꼴이 되어 조건을 만족하지 않는다.=> 따라서, rank를 부여하고 idx와 같이 비교한다. 3. 복기문제를 풀고나서 알았는데, 이는 좌표압축 기법을 사용하는 문제였다.차이..

BOJ Linkhttps://www.acmicpc.net/problem/1965     풀이 과정관심사는 최대 상자의 개수이다. 어떤 상자들로 최대를 만들었는지는 상관이 없다. 따라서,when cost[i] > cost[0~i-1] 일 때,dp[i] = (dp[0 ~ i-1] 중 최대 값) +1(i번째 상자 포함)로 놓았다. 이는 2중 for문으로 구현 가능하다.  제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;class Main { public static void main(String[] args) throws IOException..

BOJ Linkhttps://www.acmicpc.net/problem/1679   풀이 과정DP + 그래프 탐색 문제 어떤 수를 만들 수 있는지 판별보다, 만들 수 있는 모든 수를 기록해 놓는게 빠르다.그래프 탐색을 통해 "DP[만들 수 있는 수] = 도달한 depth" 를 적는다. 같거나 더 많은 depth로 도달했다면 가지치기 한다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;class Main { static int N, K, num[], MAX, DEFAULT; static int[] vst; public sta..

BOJ Linkhttps://www.acmicpc.net/problem/1622   풀이 과정1.  a의 부분 수열의 순열이자 b의 부분 수열의 순열이 되는 가장 긴 문자열 x의 사전 순으로 가장 앞에 오는 것을 출력? 한마디로 a와 b가 공통으로 가진 원소 집합을 찾아 정렬하면 된다. map으로 a와 b의 를 저장한 뒤 공통 원소만 뽑는다.둘 다 어떤 원소를 가지고 있다면, 둘 중 더 적은 개수가 공통 원소가 된다. 2. 입력에는 빈 문자열이 올 수 있으며, EOF 처리를 해야함 전자의 조건은 놀랍게도 명시되어 있지 않다. 유추해서 처리해야 한다.if ("".equals(A) || "".equals(B)) { System.out.println(); continue;}while ((A = br..

BOJ Linkhttps://www.acmicpc.net/problem/1474    풀이 과정 1. 채워야할 _ 개수를 구하는 방법 M => 만들어야 할 단어 길이N => 사용할 단어의 개수S => N개 단어의 길이 합U => 빈 공간의 개수 == N - 1 min : (M - S) / U => 빈 공간마다 필요한 최소 _의 개수remain : (M - S) % U => 추가로 사용해야 할 _ 개수  remain = 0이라면, 모든 빈 공간을 같은 개수의 _로 채울 수 있음을 의미한다.0이 아니라면, 일단 모든 빈 공간을 min 개수로 채운다.이후 각 공간마다 최대 1개씩 더하며 remain을 0으로 만든다.모두 같게 만드는 것이 불가능한 경우 단어와 단어 사이에 있는 _의 개수의 최댓값과 최솟값의 차..

BOJ Linkhttps://www.acmicpc.net/problem/1325      풀이 과정일반적인 그래프 탐색이나, 시간초과 조건이 조금 빡세서 정답률이 18%였다.인접 배열대신 리스트로 구현해야했고, 단방향 그래프의 간선 순서가 반대로 주어짐에 주의해야 했다. int n = next.get(j);if (!vst[n]) { vst[n] = true; q.offer(n); cnt++;} 한 번 시간초과를 받은 이유에 list.get(j)를 3번 적은 동작이 있었다. 자바가 내부적으로 캐싱을 해주지 않을까 해서 썼는데, 안해준다고 한다. 이는 단순히 변수로 저장하고 써서 통과했다.  제출 코드import java.io.BufferedReader;import java.io.IOExce..

BOJ Linkhttps://www.acmicpc.net/problem/1515      풀이 과정문자열의 길이는 3천 이하이므로, 그리디만 적용하면 널널하게 탐색할 수 있어서 매 탐색마다 int to string 변환을 했다. 1. 현재 숫자 num으로 문자열의 부분을 구성할 수 있을 때, 더 큰 숫자로 구성하는게 최적인 경우는 없다 => 그리디e.g. 112 같은 경우, 무조건 작은 수 부터 (1 -> 12) 이루는게 최적이다. 더 큰 수(11 -> 12)는 잘해봤자 같은 값이다. 1-1. 탐색의 시작은 0번째 인덱스에 쓰인 num부터 진행한다. ( 또한 숫자가 0인 경우, 가장 작은 숫자는 10이다.)1-2. 이후 num을 1씩 올려가며 문자열의 부분을 구성할 수 있다면 항상 최적이다. 2. 현재 ..