Lewis's Tech Keep

참고 : 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..

참고 : www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net - dp 문제 - dp[i][j] : i를 구하기 위해 필요한 j 횟수 (0~i 까지 숫자를 이용) - dp 로 해야했으나 recursive하게 backtracking 으로 접근 : 실패 더보기 import java.io.*; import java.util.*; public class Solution { private static int n, m; private static int[] arr; private static boolean[] isUsed; private static int count = 0; private stati..

참고: www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net - dp 문제 - dp[i][j] = i, j 칸에서 가능한 루트 갯수 더보기 import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] maps = ..

참고 : www.acmicpc.net/problem/1890 - dp 문제 - dp 시도하다가 안되서 dfs로 풀려다 시간초과 - top-down 방식 좀 더 자유롭게 쓸 수 있게 더보기 import java.io.*; import java.util.*; class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } public boolean isInside(int N) { return this.x >= 0 && this.y >= 0 && this.x < N && this.y < N; } } public class Solution { private static int N; private static int count; ..

참고: www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net - dp 문제 - 풀이 보고 함 - bfs 로 풀려고 했으나 시간 초과 - dfs + 메모이제이션 이용한 dp로 푸는 방법이 결론.. 더보기 import java.io.*; import java.util.*; class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } public boolean canMove(int..

참고 : www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net - 다익스트라 문제 - 풀이를 보고 품 - 어떻게 해서 최단 거리를 구할 지 아이디어가 핵심 - d[N] : x에서 시작점까지의 최단 거리 - rd[N] : 시작점에서 x까지의 최단 거리 더보기 import java.io.*; import java.util.*; class Edge { int vertex; int weight; public Edge(int vertex, i..