SH

https://www.acmicpc.net/problem/1599 ng를 하나의 문자로 처리하는 것과 ang, angle 처럼 한 단어가 prefix 부분집합이 되는 경우는 더 짧은 것이 우선순위가 높음에 주의 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;class Main { //a b k d e g h i l m n ng o p r s t u w y public s..

https://www.acmicpc.net/problem/1647 1. MST 구성 (크루스칼 사용)2. total weight - max weight인 간선을 하나 뺀 값 출력 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.List;import java.util.StringTokenizer;class Main { static class Edge { int..

https://www.acmicpc.net/problem/1577  시행 착오: 1. N이 가로를 의미한다. 배열은 정사각형이 아니므로 N이 세로를 의미하면 답이 달라진다. (도로 정보까지 맞춰서 반대로 저장하면 상관없음) 2. 도로를 기록할 때 양방향으로 저장했다가 틀렸다.if (a == c) {load[b][a][0] = d;load[d][a][0] = b;} else {load[b][a][1] = c;load[b][c][1] = a;} 이러면 한 지점에 연결된 도로의 정보가 2개 이상이면 모두 기록하지 못하고, 덮어 씌워진다.  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import..

https://www.acmicpc.net/problem/1988 dp문제 처음에 누적합이 떠올랐는데조합으로 원소 뽑으려면 3000!/(3000-n)! * n!이여서 불가능했다. 이후 문제분류 보고 풀음  처음엔 dp[N+1][B+1][2][2]  = dp[N][B][잠 or 안잠][ 준비 or 준비아님]로 생각했다가경우의 수를 구체화 하다보니 더 간결하게 만들 수 있었고, 다음과 같은 식을 세우고 풀었다.// 1. 잠을 잔 경우s[n][b] = Math.max(ns[n-1][b-1], s[n-1][b-1] + cost[n]);// 1-1. 안잤었음, 잠횟수 소모, 안잤었으니 준비 시간임ns[n-1][b-1]// 1-2. 잤었음, 잠횟수 소모, 잤었으니 준비 시간 아님s[n-1][b-1] + cost[n..

https://www.acmicpc.net/problem/1584 다익스트라 or 0-1 BFS 문제 다익스트라로 풂 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Comparator;import java.util.PriorityQueue;import java.util.StringTokenizer;class Main { static class Node { int r, c, d; Node(int r, int c, int d) { this.r = r; this.c = c; this.d..

https://www.acmicpc.net/problem/1937  이전 문제랑 거의 똑같다.https://sh3542.tistory.com/251 [백준 1520] 내리막 길 - JAVAhttps://www.acmicpc.net/problem/1520 두 코드를 비교했을 때,재귀적으로 경로를 찾아가는 것은 동일하다.다만, 방문처리 (코드에선 -1 or 0)을 하지 않으면 불필요한 재귀가 반복되어 시간초과였다. ACimporsh3542.tistory.com dp[r][c] = 1은 지역을 방문했다는 것은 그 지역의  대나무를 먹었다는 뜻이기에 +1 하는 의미도 있고,방문하지 않았음 (dr[r][c] = 0)일 때 와 구분하는 역할도 한다. 처음부터 배열을 1로 채우면 불필요한 탐색이 추가되므로 시간초과를..

https://www.acmicpc.net/problem/1520 두 코드를 비교했을 때,재귀적으로 경로를 찾아가는 것은 동일하다.다만, 방문처리 (코드에선 -1 or 0)을 하지 않으면 불필요한 재귀가 반복되어 시간초과였다. ACimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { static int solve(int r, int c) { if (dp[r][c] != -1) { return dp[r][c]; } if (r == 0 && c == 0..

https://www.acmicpc.net/problem/1501 같은 단어려면1. 0번째와 len-1번째 알파벳이 같음2. 사용된 알파벳 개수가 같음 판별하려면 1번을 Pos 클래스로 놓음2번을 알파벳별로 카운팅 하는 대신 정렬해서 key로 씀 Map> 사용 이후 M개의 문장을 공백기준으로 파싱하고, 각각 정렬해서 key로 씀map에 key가 있으면 Pos List 비교해서 정답 누적후 출력 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import jav..

https://www.acmicpc.net/problem/1743 그래프 탐색 문제 인접한 '#'끼리 붙여 도형을 만들었을 때, 넓이가 가장 큰 것(의 넓이) 출력 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 InputStreamR..

https://www.acmicpc.net/problem/1460  접근이 어려워서 포스팅 보고 시작했다.https://magentino.tistory.com/95  1.  씨앗을 최대 두 종류 포함했는지 판별 농장을 범위를 선택하고, 포함된 과일 씨앗를 체크한다. X씨앗을 두 개 뽑은채로 농장 범위를 선택한다. O m[i][j]가 두 개의 씨앗 중 하나라면 dp[i][j] = 1로 놓는다.그러면 dp가 0-1 값으로 초기화된다. 2. 씨앗 두 개씩 뽑기씨앗은 8가지 밖에 없고, 순서도 상관 없으므로 조합으로 뽑는다.  3. dp 도출dp[i][j] = 좌표 (0,0)부터 (i,j)까지 고려했을 때, 준규가 가져갈 수 있는 농장의 최대 길이 dp[i][j] = 0이라면, 0번 씨앗 or 선택하지 않은 씨..