문제접근DP 사용해서 이전의 결과값을 사용해서 효율적인 계산을 진행하였다.예시스티커를 뗀 부분이 O이고찢겨진 부분은 X라고 하자.(0,2) 위치의 스티커를 뗀 경우는 아래와 같이 나누어진다. 지금 목표는 스티커를 뗀 경우 중 가장 큰 값을 얻었을 때이기 때문에 이때 둘 중에 큰 값을 선택하고 (0,2) 위치의 스티커 값을 더해주면 된다.이외에 아무것도 떼지 않은 경우(1,1) 위치의 스티커를 뗀 경우 (0,3) 위치의 스티커를 뗀 경우는 아래와 같이 나누어진다. (1,2) 위치의 스티커를 뗀 경우(1,1) 위치의 스티커를 뗀 경우해당 값 중에 큰 값을 선택하고 (0,3) 위치의 스티커 값을 더해주면 된다. 그러면 아래와 같은 점화식을 얻을 수 있다.구한 점화식을 코드에 적용하면 아래 코드와 같다.코드im..

문제접근2*1 의 경우는 1가지2*2의 경우는 2가지2*3의 경우는 3가지...규칙이 있는 것을 찾아냈다.예를 들어 n=5인 경우, 마지막 2*1 부분  빼고 모두 차있는 경우 + 마지막 2*2 부분이 가로로 채워져 있고 모두 차있는 경우두 가지 경우를 더한 경우의 수가 모든 경우의 수이다.점화식 : dp[i] = dp[i-1] + dp[i-2]코드import java.util.*;public class Main { static int[] dp; static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); dp = n..

구간 합 구하기 5참고 : https://www.acmicpc.net/problem/11660접근해당 문제는 이차원 배열에서 누적합을 구해서 주어진 구간의 합을 구해야 한다고 생각했습니다.map이라는 N * N 의 2차원 배열에 누적합을 계산해서 저장시간 복잡도 : O(N^2)(i열 , j-1행의 누적합) + (i-1열, j행의 누적합) - (i-1열, j-1행의 누적합) + (i열, j행)i 열 j 행 의 누적합은 아래 식을 통해서 구할 수 있습니다.주어진 구간에서의 합 구하기해당 과정을 통해서 점화식을 구하면 아래와 같습니다.- 코드를 구현할 때는 map, sumMap의 크기를 N+1로 해서 진행.전체 코드package baekjoon_day01;import java.io.*;import java.u..