본문 바로가기

다이나믹프로그래밍26

[백준 2167] 2차원 배열의 합 www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 누적합을 사용하여 시간을 줄이는 문제이다. (i,j)부터 (x,y)까지 다 더해도 상관없긴 하나 tle가 날꺼 같아서 col기준 누적합을 사용했다. i는 시작 row, x는 마지막 row col기준 누적합을 사용하므로 sum[?][y] - sum[?][j-1]을 해주면 각 row에 대한 합이 나온다. #include using namespace std; int m, n; int su.. 2020. 12. 11.
[백준 15486] 퇴사 2 www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net dp 사용문제인데 까다롭당.. dp[n]은 n일까지 일했을 때 받을 수 있는 최대 금액이다. n일에 일한건 n일에 못받는다. 최소 n+1일에 받을 수 있음 문제의 핵심은 일을 끝마쳤을 때의 날짜의 금액 dp[arr[i][0] + i ]값을 업데이트 해주는 것이다. 하지만 dp[arr[i][0] + i ] = max(dp[arr[i][0] + i], dp[i] + arr[i][1]).. 2020. 11. 26.
[백준 17626] Four Squares www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 자주 보이는 dp 유형 중 하나 근데 풀 때마다 막막하다... 점화식을 세우기 위해 숫자 하나씩 해본다. 1 = 1 * 1 2 = 1 * 1 + 1 * 1 3 = 1 * 1 + 1 * 1 + 1 * 1 4 = 2 * 2 5 = 2 * 2 + 1 * 1 .... 10 = 3 * 3 + 1 dp[n]은 제곱수 합으로 표현할 때 사용하는 숫자의 최소 개수라고 정의한다. 그러면 n이.. 2020. 11. 26.
[leetcode 118] Pascal's Triangle Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example: Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 문제 풀이 난이도 easy dp로 구현하면 되는 문제이다. 자바로 구현방법 익히기!!! class Solution { public List generate(int numRows) { List tr = new ArrayList(); if(numRows == 0){ return .. 2020. 11. 19.

티스토리툴바