끄적끄적

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

BOJ Link https://www.acmicpc.net/problem/1202   풀이 과정우선순위 큐를 2개 사용한다.보석을 무게 기준 오름차순 정렬한다. 가방을 무게 기준 오름차순으로 우선순위 큐(kq)에 넣는다. (kq)에서 무게가 작은 가방부터 탐색하며, 다음 과정을 반복한다. 1. 현재 보석을 가방에 담을 수 있다면, 우선순위 큐(vq)에 보석의 가치를 내림차순으로 저장한다.해당 보석을 vq에 넣었으므로, 다음 가방에서 보석을 넣을 수 있는지를 탐색할 시작점인 idx를 올린다. 2. 담을 수 없다면, 뒤의 보석들도 담을 수 없으므로 탐색을 종료한다. 3-1. vq에는 현재 가방으로 낼 수 있는 가치가 내림차순으로 정렬되어있다. peek값을 ans에 누적하고 가방과 보석을 사용 처리한다.3-2..

BOJ Link https://www.acmicpc.net/problem/1011  풀이 과정다른 행성에 도달하기 직전의 칸은 k가 1이여야 한다.그렇다면, 러프하게 1 - (k올림) - max - (k내림) - 1의 꼴로 k가 전개됨을 알 수 있다. 몇 개의 케이스를 만들어 봤을 때, 1. k가 올림 - 내림 - 올림 등인 변칙적인 경로일 때 값이 최적인 경우는 없다고 생각했다.2. 값을 누적했을 때, 더이상 k를 증가시킬 수 없다면, 경로에 사용되었던 k들로 모든 답을 구성할 수 있다고 생각했다.(아마 최대 2번 더 사용해서) 그래서, 현재 이동한 거리 sum과 k를 비교하여,1. dis 2. dis > sum + k + (k + 1)라면, 사용된 k중 가장 큰 수부터 비교하며 최적해를 찾는다.로 구..

BOJ Link https://www.acmicpc.net/problem/1195     풀이 과정아이디어를 떠올리긴 쉽고, 구현은 실수하기 쉬운 문제였다. 1or2의 이진 값이기에 비트마스킹을 적용할 수 있고,각 기어의 길이는 100이하이므로,first 기어의 왼쪽/오른쪽에 값이 0인 100길이의 인덱스를 pad로 놓은 first[100 + first.len + 100]배열을 구성하여인덱스 처리를 쉽게 할 수 있다. 후자의 방법이 생각은 났지만 사용하지 않았다. 쉽다고 착각하여 무작정 코드를 작성하고 테스트케이스를 넣으면서 쓴맛을 봤다.  second 기어가 first 기어의 왼쪽에 있을 때, 겹칠때, 오른쪽에 있을 때 3개의 케이스를 나누어 완전탐색했다.이 때, 기어가 겹치는 2번째의 경우는 seco..