SH

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

BOJ Linkhttps://www.acmicpc.net/problem/1261   풀이 과정최단 거리, 다익스트라, 0-1 BFS 분류로 되어있는 문제다. 나는 우선순위 큐와 가중치를 통해 풀이했다. 일반 BFS를 사용할 수 없는 이유어떤 행렬에 도달할 때, 뺑 돌아오는 길이 최적해일 수 있다.따라서 방문체크 배열을 통해 한 번 방문한 곳을 다시 방문하지 않는 로직은 적용이 불가능하다.그러므로 모든 경로를 고려해야 하는데, 이 때 배열은 최대 100*100이므로, 모든 경우를 탐색할 순 없다. 핵심 아이디어별도의 배열에 방문 여부 대신 가중치를 기록한다.이 때, 현재 행렬 가중치 + 인접한 곳으로 가는 비용 인접한 행렬을 갱신하고, 다음 탐색을 가중치를 정렬 기준으로 삼는 우선순위 큐에 넣는다. (큐도..

BOJ Linkhttps://www.acmicpc.net/problem/1022   풀이 과정배열 돌리기류? 달팽이류? 단순 구현문제다.어떤 좌표에 쓰인 수를 찾는 방법은 다음과 같이 구현했다. 초록색 좌표의 수를 찾으려 할때, 빨간색 영역을 미리 구해놓고, 파란색 좌표부터 반시계 방향으로 탐색하며 구해준다.  빨간색 영역의 크기는 다음과 같다.int max = Math.max(Math.abs(r), Math.abs(c)) - 1;int areaSize = (1 + max * 2) * (1 + max * 2); 파란색 좌표에는 무조건 빨간색 영역의 사이즈 +1인 수가 위치하며, c좌표 또한 +1 해준다.int nr = max;int nc = max + 1;int num = areaSize + 1;이후 델..

BOJ Linkhttps://www.acmicpc.net/problem/1241  풀이 과정입력을 배열에 저장함과 동시에, 각 숫자를 가진 사람의 개수 cnt를 map에 같이 merge해준다.이후 배열을 순차탐색하며, i번째 원소의 약수의 cnt를 모두 더한 값 sum을 구해준다. 이때,해당 원소의 sum을 구한적이 없다면, 구하여 result map과 stringbuilder에 저장한다.구한적이 있다면, result map의 값을 사용하여 stringbuilder에 저장한다. 탐색을 마쳤다면 출력한다. 핵심 아이디어는 다음과 같다. 1. 어떤 자연수 M의 약수를 N이라고 하면,M의 N집합을 구하기 위해 1 ≤ N ≥ sqrt(M)이하인 범위만 탐색하면 된다. 2. 어떤 N이 존재한다면, N * M/N ..

BOJ Linkhttps://www.acmicpc.net/problem/1099   풀이 과정인덱스 관리가 까다로웠다. 핵심 로직은 다음과 같다.dp[i] = 문장을 i번 째 인덱스 까지 잘랐을 때, 해당 부분 문자열을 이룰 수 있는 최소 비용모든 단어는 0번 또는 그 이상 사용할 수 있기 때문에, 어떤 단어로 구성하였는지는 기록하지 않는다. origin - 원본 문자열 sector - origin의 부분 문자열word - 비교할 단어 1. 부분 문자열 구성 sector와 word를 비교하려면, 두 문자열의 길이가 같아야 한다. 다음과 같은 비교는 불가능하다.origin=abcdeword=abc, a  다음과 같은 경우는 비교 대상이다. 고려해야 한다.origin=abcdeword=bdc , bcd, f..

BOJ Linkhttps://www.acmicpc.net/problem/1091  풀이 과정단순 구현 문제이며 시간은 널널하다.다소 이해가 힘든 문제를 파악하고, 카드를 섞는 방법을 코드로 표현하는 것에 중점을 둔 문제같다. origin, next, now, goal, suffle 5개의 배열을 사용한다. cnt는 카드를 섞은 횟수이다. origin - 초기 카드 상태next - 카드를 섞은 이후 카드 상태now - 현재 카드 상태goal - 목표 카드 상태suffle - 카드를 섞는 패턴 각 배열의 초기화 이후, 다음과 같은 과정을 반복한다. 1. goal과 now를 비교하여 같다면 cnt 출력 2. cnt != 0이고, origin과 now를 비교하여 같다면 -1 출력(한 싸이클을 돌고나서도 초기 상..

BOJ Link https://www.acmicpc.net/problem/1239   풀이 과정1. N이 매우 작으므로 순열을 사용했다. (N 순열로 N개의 원소를 뽑는 모든 경우의 수를 구한다. O(8P8 = 40320)단, 뽑은 원소의 누적합으로 배열을 구성한다.when dep = 0,  pick[dep] = arr[i];when dep > 0, pick[dep] = pick[dep - 1] + arr[i]; + 정확히는 같은 것이 있는 순열이다. 하지만 문제 특성상arr[] = {A1(10), B(20), A2(10)} 일 때,pick[] = {A1,B,A2}를 뽑은 경우와 {A2,B,A1}를 뽑은 경우의 결과는 같으므로 처리하지 않았다.답인 경우의 개수를 세야한다면 처리해야 한다. 또한, 중복 순..

BOJ Link https://www.acmicpc.net/problem/1245  유의할 점명시되지 않은 조건이 있다.=> 산봉우리의 높이는 0이 될 수 없다. 모호한 조건이 있다.=> 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. 이에 따라, 고려할 케이스// input3 30 0 00 0 01 0 1// output2 // ans1 // wrong ans 풀이 이후, assert로 N=1 / M=1인 케이스는 없음을 확인했다.제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import j..