Lewis's Tech Keep

참고 : www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net - dp 문제 - 풀이를 보고 풀었다. 아이디어를 찾기가 힘들었다. - dp[N][L][R] : dp[N-1][L][R] * (N-2) + dp[N-1][L-1][R] + dp[N-1][L][R-1]; 더보기 import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner..

참고 : www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 dp[3] 123 + 4 : 하나만 바꿈, dp[2] 12 + 34 : 둘 다 바꿈 ) - 나머지는 중복되므로 dp[i] = dp[i-1] + dp[i-2]가 성립. - 경우의 수에 따라 vip 좌석 전 후 경우의 수 : a*b (ex a : 2가지 b: 2가지 = a*b) 더보기 import java.util.*; public..

참고 : programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr - 트리 순회 - y좌표가 가장 큰 값 -> 루트 노드 - y좌표가 같다 = 같은 레벨에 있는 노드 - y좌표가 같고 x좌표가 적다 -> 왼쪽 자식 노드일 가능성이 있다. - y좌표가 같고 x좌표가 크다 -> 오른쪽 자식 노드일 가능성이 있다. - 이후 트리 구성 후 전위 순회, 후위 순회를 재귀로 돌아주고 각 순서를 answer에 넣어준다. 더보기 import jav..

참고: www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net - dp 문제 - LIS 를 잘 이용해야 함 - 정렬이 필요한 숫자의 최소 수 : 증가 수열의 값이 최대가 되는 값의 갯수 => LIS가 필요함 더보기 import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); in..

참고 : www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net - dp 문제 - dp[i][0] : dp[i-1][0] + dp[i-1][1] ( = i-1번째의 최소값, 최대값 (0번, 1번이 해당 i번째로 이동가능)) + s[i][0] - dp[i][1] : dp[i-1][0] + dp[i-1][1] + dp[i-1][2] ( = i-1번째의 최소값, 최대값 (0번, 1번, 2번이 해당 i번째로 이동가능)) + s[i][1] - dp[i][2] : dp[i-1][1] + d..

참고 : www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net - 다익스트라 - 기본 다익스트라 구현 문제와 같음. bfs + adj 리스트 구현 잘 생각할 것. 더보기 import java.util.*; class Edge implements Comparable { int vertex; int weight; public Edge(int vertex, int weight) { this.vertex = vertex; this.weight ..

참고 : www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net - dp 문제 - dp[i] : dp[i] + dp[i-1] (1~9 사이일 경우) - dp[i] : dp[i] + dp[i-1] + dp[i-2] (10~26사이일 경우) 두자리 수 고려 - 가장 깔끔하신 분 풀이 보고 찾아보았다. (github.com/hotehrud/acmicpc/blob/master/algorithm/dp/2011.java) 더보기 import java.util.*; public class Sol..

참고 : www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net - dp문제 - dp[i] : i번째에 더할 수 있는 모든 경우의 수 (= dp[i-1] (i-1 + 1의 경우) + dp[i-2] (i-2 + 2의 경우) + dp[i-3] (i-1 + 3의 경우)) 더보기 import java.util.*; public class Solution { private static int n; private static int[] dp; public static void main(String[] args) { Scanner sc = new Scanner(System.i..