Lewis's Tech Keep

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

출처 : www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net - dp 문제 - 점화식 구하는 짬밥을 계속 키워 나가자 - dp[i] : i번 째 1,2,3 으로 만들 수 있는 경우 수의 값 더보기 import java.util.Scanner; // 해당 코드를 이용하여 input & output 만 받으면 된다. public class Solution { public int solution (int n) { int[] dp = new int[12]; dp[1] = 1; dp[2] = 2; dp[3] = 4; for(int i=4; i

- 간단한 dp 문제 - 하지만 못 품 - 필요 아이디어 - dp[i] => i의 숫자의 경우에 필요한 최소 단계 수 더보기 import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int[] dp = new int[a+1]; dp[1] = 0; for(int i=2; i

- dp 문제 - dp 문제를 풀 때 어떤 값을 기준으로 찾을 지 생각하는 것이 중요하다고 생각합니다. - bottom-up 방식 연습 - triangle[x] = 0~x번 째 까지의 최대 비용의 아이디어를 가지고 푸는 문제 더보기 import java.util.*; class Solution { public int solution(int[][] triangle) { int row = triangle.length; for(int i=1; i< row; i++) { int col = triangle[i].length; for(int j=0; j

- dp 컨셉을 좀 더 자세히 파고 들어야 했다. - 첫 차례에 시작한 경우 & 첫 차례에는 시작하지 않고 두 번째부터 시작한 경우의 최대값을 구해야 했다. - 세 번째부터는 첫 차례의 값을 가지고 + 세 번째 값을 더 하는 것이 당연히 더 크거나 같다 (모든 수가 0이상이므로) - 네 번째부터는 두 번째부터의 값을 가지고 + 네 번째 값 더하는 것이 당연히 더 크거나 같다 (모든 수가 0이상이므로) - 따라서 두 가지 경우에 대해서만 계산해서 최대값을 구해주면 되는 문제였다. 더보기 class Solution { public int solution(int[] money) { // bottom-up // 0번째 최대 비용 계산 -> 1번째 최대비용 계산 // 0번째 부터 계산 int value1 = mo..

- 해보다보니 피보나치 인 걸 알게됨 - 피보나치 dp 는 그냥 메모이제이션만 잘 해주면 갈무리 됨 더보기 class Solution { // 1 1 2 3 5 // n=1 -> 1 // n=2 -> 2 // dp // int[] public int solution(int n) { final int CONSTANT = 1000000007; int[] dp = new int[n+2]; dp[0] = 1; dp[1] = 1; for(int i=2; i