목록전체 글 (181)
Lewis's Tech Keep
참고: 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..
참고 : www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net - dp 문제 - dp[i] : dp[i-1]* 2 + dp[i-2] 의 공식이 성립 (왜 성립하는 지 알아보고 수정할 것) - 아주 좋은 링크 : m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220784781196&proxyReferer=https:%2F%2Fwww.google.com%2F 더보기 import java.io.*; import java.util.*; public class Solution { private static int n; private static int[] dp..
참고 : www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 아주 좋은 풀이 링크를 보고 풀었다. 갓.. (m.blog.naver.com/occidere/220788208204) - dp 문제 - LIS 개념을 알면 잘 풀 수 있었던 문제. 좋은 거 배웠당. - DP[i] : 1부터 i까지 최대로 감쌀 수 있는 박스 갯수 (증가 수열 갯수) 더보기 import java.io.*; import java.util.*; public class Solution { private..
참고 : www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net - dp 문제 - mod 연산 마지막에 한번 더 해주거나 감싸줘야하는 거 잊지않기 - dp[i][j] : i를 구하기 위해 필요한 j 횟수 (0~i 까지 숫자를 이용) 더보기 import java.io.*; import java.util.*; public class Solution { private static int n, m; private static int[][] dp; private static int MOD = 1_000_000_000; public static void main(String[] args) { Scann..