SH

https://www.acmicpc.net/problem/13549 0-1 bfs 일반 BFS에 정렬 기준이 없는 큐를 사용하고, 가중치 1인 탐색을 먼저 넣고 0을 이후 넣는 코드를 작성했다면다음 탐색에서 둘 다 정답일 때, 최단거리가 아닌 오답(가중치 1이 더해진 값)이 출력될 수 있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.StringTokenizer;class Main { public static void ma..

https://www.acmicpc.net/problem/1621 dp[i] = dp[i-1] + 현재 바나나if (dp[i] > dp[i-k] + k개 바나나를 c 비용으로 옮기는 비용) prev[i] = k + 여기서, 바나나를 k개 옮겼을 때와 하나씩 옮겼을 때 비용이 같은 경우도 걸러짐(답이 여러 개 존재하면, K개 들고 가는 횟수가 가장 적은 것을 구해야 한다) 이후 prev를 N부터 순회하며,k가 적혀있다면, 왼쪽을 기록하고 k칸 전으로 이동한다.0이 적혀있다면, 1개 옮긴 것이므로 1칸 전으로 이동한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.u..

https://www.acmicpc.net/problem/2011 dp언뜻 보기에는 쉬우나, 고려해야 할 경우가 많아 초기화가 까다로운 문제다. 1. 유효한 수의 범위는 1~26이다.따라서, 한 자리 수는 0이면 안된다. 2. '수'에 다음과 같은 경우는 포함되지 않는다. 01 001 0023따라서, 두 자리 수는 10~26 범위만 유효하다.또는, 첫 자리가 0이 아니고 27보다 작으면 된다. 3. 1번과 2번에 따라, 암호의 첫 번째 수가 0이면 경우의 수는 무조건 0이다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static vo..

https://www.acmicpc.net/problem/1594 dp 일반 dp는 i번째까지 구성했을 때 값이나 컨디션만 필요하다. 근데 이 문제는 경로도 요구한다.따라서, dp와 path 배열을 같이 기록해준다. dp[i-2] or dp[i-3] 에 대해,더 높은 값(품질)을 얻을 수 있거나, 똑같은 값이어도 path를 사전 순으로 앞당길 수 있다면 갱신한다. 배낭 문제 + 역추적으로 풀어보려 했었는데, 되는지 확신을 가지지 못해서 경로를 직접 저장했다. import java.util.Arrays;import java.util.Scanner;public class Main { static String number; static int n; static int[] dp; // 품질 저장 stat..

https://www.acmicpc.net/problem/1715 숫자가 작은 카드부터 더하는게 최적이다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); PriorityQueue q = ne..

https://www.acmicpc.net/problem/2064 1.String[] ipByte = br.readLine().split("\\."); regex에서 "."은 임의의 한 문자를 의미한다. 따라서, 모든 문자를 구분자로 사용하므로 빈 배열이 생성된다.마침표 자체를 표시하기 위해 이스케이프 두 번 처리해준다. 2.%32s : 왼쪽에 32 - s.len 만큼 공백 채움%-32s : 오른쪽에 32 - s.len 만큼 공백 채움 항상 bit에서 0을 채워야하면 왼쪽이여서 몰랐었다. 해당 문제는 -를 붙여서 오른쪽을 채운다.또한, 찾아보니 %S는 string을 uppercase로 표시해준다. %D는 없고 UnknownFormatConversionException을 던진다고 한다. 3.32-m에서 m..

https://www.acmicpc.net/problem/1332 브루트포스 문제 시간복잡도O(2^N), N = 50, 2^50 = 1,125,899,906,842,624에 가깝다.때문에, 문제 분류는 브루트포스만 적혀있음에도재귀/그래프 탐색/dp 뭐든간에 같이 쓰고 prune, memo 등으로 최적화 해야 한다.나름 최단경로 문제이므로, 나는 BFS를 썼다. 최적화로 다음 경우를 쳐낼 수 있으면 풀릴 것 같다.50 101 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 + 개인적으로는 안좋은 문제같다.복잡도 측면에서, 이정도 최적화로 통과하겠다는 확신을 가지기 어렵고,최적화 -..

https://www.acmicpc.net/problem/7774 그리디, 정렬 접근(그리디)- 두 번째 멀티탭은, 최대한 많이 연결한다.- 첫 번째 멀티탭은, 두 번째 멀티탭을 최대한 많이 연결하게 하는 선에서 최소로 사용해야 한다.- ai, bi >= 1이므로, A플러그 - 첫 번째 - 두 번째 꼴을 만들 수만 있다면 최적이다(손해는 안보고, 이득은 볼 수 있으므로 무조건 연결해도 된다.) 풀이 B플러그가 가장 많은 두 번째 멀티탭을 연결하고 시작한다.0개라 연결할 수 없거나, 연결하면 손해인 경우는 N == 0 || M == 0으로 이미 걸렀기 때문이다. 이후, B플러그가 다 사용될 때 까지 A플러그가 최대인 첫 번째 멀티탭을 꼽는다.B플러그를 다 사용했다면, 연결된 첫번 째 멀티탭의 A 플러그에..

https://www.acmicpc.net/problem/1327 불태웠다. 여러모로 소득이 많은 문제였다. 시행 착오DFS(재귀)로 구현, Set으로 매 탐색을 방문체크 했을 때도 시간초과와 오답 발생 경우의 수가 8!에 방문체크도 하기 때문에, 될까 싶어서 시도했다가 IDE에서 벌써 SOF가 발생했다.이건 그렇다쳐도, 출력이 10이여야 하는 케이스에 74가 출력됐고, 코드에는 오류가 없었다. 이유는 DFS의 탐색 순서 때문에, depth 10인 탐색보다 depth 74인 탐색이 먼저 실행되며 답을 찾았고, 이 탐색이 Set에 방문체크 되며 depth 10인 탐색은 실행되지 않았기 때문이다. 따라서 ans = Math.min(ans, cur); 는 없는 코드가 되버린다. 구현 1.BFS인건 찾았으나..

https://www.acmicpc.net/problem/2468 bfs v[][] w[][] import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Queue;import java.util.StringTokenizer;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.p..