목록전체 글 (181)
Lewis's Tech Keep
참고 : 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..
- 참고: www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net - DP 문제 - 구간 합을 미리 저장해 놓는다면 기존 O(NM)에 시간 복잡도를 가지던 합 계산이 O(1) 안에 풀리게 된다. (미리 저장해 두므로) 더보기 import java.util.Scanner; public class Solution { // prefix sum public static void main(String[] args) { Scanner sc = new S..
참고 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net - DP 문제 - dp[i][0~2] : 각 색깔별 i번 째에서의 최소 비용 (단, 0는 red, 1은 green, 2는 blue를 무조건 선택하는 경우의 수) 더보기 import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(Syst..
참고 : www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net - dp 문제 - 테이블 정의를 어떻게 하느냐에 따라 다르게 풀이 될 수 있는 점이 흥미로웠다. - dp[i] : i 번째 계단을 밟지 않는 경우의 수의 최소 값 (i-1은 반드시 선택, i-2 or i-3 번째 중에 값을 선택하는 것) 더보기 import java.util.Scanner; public class Solution { // 밟지 않는 경우의 수 체크 public static void main(Stri..