Lewis's Tech Keep

참고 : www.acmicpc.net/problem/9461 - dp 문제 - dp[i] : i번째 가ㄴㅇ장 긴 변의 길 (4번째 이후로 i-2번째와 i-3번째 가장 긴 변의 길이의 합과 같음 = 회전하므로 같은 규칙을 항상 가지게 된다.) 더보기 import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long[] dp = new long[102]; dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; for (int i = 5; i

참고 : www.acmicpc.net/problem/4949 - 스택 문제 - 문제의 조건을 해석하는데 푸는 시간보다 더 오래걸렸다. 더보기 import java.util.Scanner; import java.util.Stack; public class Solution { public int solution (int n) { return 0; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { Stack s = new Stack(); String text = sc.nextLine(); String result = "yes"; if(text.equals(".")) { break; } for(..

참고 : www.acmicpc.net/problem/2293 - dp 문제 - 점화식이 그리기 어려워 다른 분 답을 참고함 - dp[i] : i까지 도달하는 경우의 수 (dp[i] = dp[i - coin[j] ]) 더보기 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] coin = new int[n+1]; int[] dp = new int[10001]; dp[0] = 1; // 무조건 1가지 방법은 있음. for(int i=1; i

참고 : www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net - dp 문제 - 다른 사람 풀이를 찾아보니 조금 다르게 풀어서 기쁘기도 하고 신기하기도 했다. (생각을 잘 넓히는 것이 중요한 거 같다) - dp[i][0] : i번째 스티커 비용의 최대값 (단 i번째는 반드시 위를 선택) - dp[i][1] : i번째 스티커 비용의 최대값 (단 i번째는 반드시 아래를 선택) - dp[i][2] : i번째 스티커 비용의 최대값 (단 i번째는 반드시 아무것도..

참고: www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net - 백트래킹 문제 - dfs에서 찾아갈 때의 느낌과 유사하므로 잘 기억해 둘 것 더보기 import java.util.Scanner; public class Solution { private static int n; private static int s; private static int[] arr = new int[30]; private static int count..

참고 : www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net - 백트래킹 문제 - 위치상 불가능한 점을 잡는 방식을 잘 기억할 것. (신박 y 가 같은 경우, x+y 가 같은 경우, x-y 가 같은 경우는 queen 이 위치할 수 없다) 더보기 import java.util.Scanner; public class Solution { private static int n; private static boolean[] isused1 = new boolean[40]; // y pri..

참고 : www.acmicpc.net/problem/15649 - 백트래킹 기본 문제 - 따라가면서 이게 왜 백트래킹이 되는 지 왜 재귀가 필요한 지 이해함. 더보기 import java.util.Scanner; public class Main{ private static int n, m; private static int[] arr = new int[10]; private static boolean[] isused = new boolean[10]; private static void backtracking(int k) { if(k == m) { for (int i = 0; i < m; i++) { System.out.print(arr[i] + " "); } System.out.print(""); ret..

참고 : www.acmicpc.net/problem/12852 - dp & 추적 - 이전 값의 주소를 저장하는 것이 포인트 더보기 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] dp = new int[n+1]; int[] pre = new int[n+1]; dp[1] = 0; for(int i=2; i dp[i/2] + 1) { dp[i] = dp[i/2] + 1; pre[i] = i/2; } if(i % 3 == 0 && dp[i] > dp[i/3] + 1) { dp[i] = dp..