[https://www.acmicpc.net/problem/14846 14846번: 직사각형과 쿼리 첫째 줄에 N (1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 행렬의 정보가 주어지며, 각 줄은 N개의 수로 이루어져 있다. 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 번호가 매겨져 있으며 www.acmicpc.net DP와 누적합 문제다. 해당 칸을 기준으로 왼쪽 위쪽으로 존재하는 숫자들의 개수를 세어 배열에 저장한다. 배열은 3차원 배열로 행렬크기에 1~10의 개수를 각각 저장할 수 있는 11의 크기다. 검정색 부분까지의 누적합을 구하기 위해서는 빨간 부분 + 파란 부분 - 보라 부분을 해야한다. 빨간 부분에도 파란 부분에도 보라 부분이 포함되어 있기 때문에 중복 계산되므로 한 번 빼야..
DP
https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net DP와 누적합 문제다. 불도저가 왼쪽 위에서 오른쪽 아래까지 가는 길에 아래 부분은 사과가 많도록 윗 부분은 바나나가 많도록 지나가야 한다. 불도저는 오른쪽, 아래쪽, 오른쪽 아래 대각선으로 움직일 수 있다. 열을 기준으로 생각을 했다. 아래로 가는 경우에는 아래 칸이 사과인지만 확인해서 빼주면 되고 오른쪽 혹은 대각선으로 움직이는 경우는 그 열에 대해 위의 바나나나 아래 사과만 확인해주면 된다..
https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net dp 문제다. 완전 순열로 본인이 본인 것을 선택하는 경우를 제외한 순열이다. n = 2인 경우 a - 2, b - 1 이렇게 한 가지 경우다. n = 3인 경우 a - 2, b - 3, c - 1 a - 3, b - 1, c - 2 이렇게 두 가지 경우다. n = 4인 경우 a - 2, b - 3, c - 4, d - 1 a - 2, b - 4, c - 1, d - 3 a - 2, b - 1, c - 4, d - 3 a - 3, b - 1, c - 4, d - 2 a - 3, b - 4, c - 1, d - 2..
https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net dp문제다. 아이들을 옮기는데 다른 제한이 없으므로 이미 일부분 정렬되어 있는 아이들을 제외하고 움직이는 방법이 최선이다. 증가하는 가장 긴 부분수열을 구하고 전체 수열의 개수에서 부분 수열의 개수를 빼주면 된다. 배열을 순회하면서 해당 숫자를 기준으로 앞 쪽을 탐색한다. 앞 부분 숫자 중 해당 숫자보다 작은 숫자가 있다면 현재 dp배열의 값과 비교한다. if (arr[i] > arr[j]) dp[i] ..
https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net DP 문제다. 그래프 형태의 DP문제로 어떻게 해결할지 고민했다. 처음에는 BFS로 접근을 하였으나 굳이? 싶었고, 시간초과가 날 것 같았다. 두 번째 떠올린 방법은 아래로 움직이는 것은 따로 고려해줄 것이 없으므로 dp[i][j] = dp[i - 1][j]를 해준 후 해당 지점에서 왼 오로 퍼지면서 중복 방문을 방지하도록 했다. 시간 초과를 예상하긴 했지만 반례가 없을 것 같아 시도 했..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net dp 문제 유형 중 하나인 배낭 문제다. 배낭 문제는 물건의 무게와 가치가 주어지고 가방의 무게가 주어졌을 때, 가방에 담은 물건들의 가치가 최대가 되도록 하는 것이다. dp 배열을 가방에 담은 물건의 개수, 가방의 무게 제한에 대한 2차원 배열로 만든다. n개의 물건을 담을 수 있을 때, n번 쨰 물건을 담는다고 생각하자. n번 ..
