끄적끄적

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. 현재 ..

BOJ Linkhttps://www.acmicpc.net/problem/1148    풀이 과정문자열 + 구현 문제구현 자체도 까다롭고, 고려할게 많다.1 시간 복잡도를 제대로 구할 수가 없다.문제에서 단어의 개수는 20만 이하이나, 정작 퍼즐판은 몇 개를 주는지 명시하지 않았다.퍼즐판의 크기를 3*3로 준데서 적당히 작겠거니 생각하고 완전탐색해서 풀었다.2. puzzle에서 α 라는 문자를 중간에 놓았다 가정하면, puzzle로 word를 만들 수 있는 조건은 다음과 같다.2-1. word에는 α 가 포함되어 있어야 한다.2-2. word에 있는 모든 알파벳(A-Z)의 개수가 puzzle의 알파벳(A-Z) 개수보다 작거나 같아야 한다.3. byte를 쓰지 않으면 왠만한 최적화로는 메모리 초과가 난다.m..

BOJ Linkhttps://www.acmicpc.net/problem/2240  풀이 과정dp[시간][움직인 횟수][현재 위치(1번or2번)] = 먹은 자두 개수 문제에서, 1≤W≤30 이므로 움직일 수 없는 경우는 존재하지 않는다.따라서, 맨 처음 움직이고 시작한 경우(1->2)를 같이 초기화한다. 1번 위치에서 2번 위치로 움직일 때, 1번 이동하여 갈수도, 3번(1->2->1), 5번(1->2->1->2->1) ... 이동하여 갈 수도 있다.이 경우 1번 움직이는 것이 최적이지만, 어차피 갱신되므로 더 많이 움직이는 경우는 신경쓰지 않는다. 최대 이동 가능 횟수보다 덜 움직였을 때 최적일 수 있으므로, 모든 dp 인덱스를 순회하여 최대값을 찾아 출력한다.제출 코드import java.io.Buff..

BOJ Linkhttps://www.acmicpc.net/problem/2169   풀이 과정돌아올 때 최적인 경우가 존재하므로 모든 경우를 고려해야 한다. 이는 최대 1000*1000 배열이므로 최적화가 필요하다.문제에서, 로봇은 위로 이동할 수 없다. 따라서 dp[i][j]가 최적이려면, 왼/오른/위쪽에서 들어오는 경우를 고려해야 한다.경로에 상관없이 해당 행열에 도달할 때 최대값만을 기록하며, 재방문이 불가능하기에 왼/오/왼같은 탐색은 불가능하다.  먼저, 배열의 첫 행은 오른쪽으로 밖에 이동할 수 없다. 이를 초기화한다.이후엔 왼+위, 오+위의 경로를 고려한 left,right 임시 배열을 선언한 후, 둘중 최대 값으로 dp를 갱신한다. 제출 코드import java.io.BufferedReade..