DP

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DP - 연속된 합이 최대가 되도록... → dp dp[n] : n번째 원소를 포함했을 때의 최댓값 ⇒ dp[n] = Math.max(dp[n-1] + n, n) 💥 유의사항 - 부분 수열의 합은 절대 0보다 작을 수 없으므로, 0 이하로 값이 나오게 되면 dp를 초기화하고 다시 최댓값을 구한다! - answer이 long 형으로 선언되어 있으므로, long형으로 계산해야 오류가 나지 않는다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ..

📖 문제 18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 💡 풀이 방식 • DP dp[i][j] : 1~i번 까지 학생이 높이가 j인 탑을 만드는 경우의 수 i번째 학생이 해당 블럭을 사용하는 경우와 사용하지 않는 경우의 수를 더한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DP dp[ j ] : 금액 j를 낼 수 있는 방법 수 (dp[n - 화폐 종류1], dp[n - 화폐 종류2], ...) ⇒ dp[ j ] = dp[ j - money[i] ] 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import java.util.*; class Solution { static final int MOD = 1_000_000_007; public int solution(int n, int[] money) {..

📖 문제 17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. www.acmicpc.net 💡 풀이 방식 • DP 1. M*M 크기의 2차원 배열 dp를 만든다. dp[ i ][ j ] : 과일 종류 j개 中 i개를 훔치는 경우의 수 2. dp배열의 초기값을 채운다. 과일 i종 중 중 i개 훔치는 경우의 수 : 1 과일 1종 중 중 i개 훔치는 경우의 수 : 1 3. 나머지 원소들은 점화식을 통해 채운다. dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

📖 문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 💡 풀이 방식 • DP (0,0)부터 O 표시된 칸까지 가는 DP 한 번,O 표시된 칸부터 오른쪽 아래의 점 (N-1, M-1)까지 가는 DP 한 번해서총 2번의 DP를 진행하며 이동 경로의 수를 나타내는 2차원 배열 dp를 채웠다. 이 때 dp를 채우기 위한 점화식은 아래와 같다. dp[i][j] = dp[i-1][j] + dp[i][j-1];// 오른쪽과 아래쪽으로만 이동가능하다고 했으므로 (0,0)부터 오른쪽 아..

📖 문제 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 💡 풀이 방식 • 조합 (DP) 파스칼 삼각형을 모두 왼쪽으로 밀었다고 생각하고 2차원 배열을 채운다. 맨 왼쪽 줄(= 0번째 열) 과 행=열인 칸은 값을 1로 채운다. 나머지 (i, j) 위치의 칸은 왼쪽 위 칸 (i-1, j-1)과 바로 윗 칸 (i-1,j)의 합으로 채운다. dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 점 (R,C)부터 길이가 W인 삼각형의 합을 구한다. 이 때 삼각형 모양으로 범위를 제한하기 위해 변수 tmp를 활용하며, 현재 행..

📖 문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 💡 풀이 방식 • 다익스트라 필요 자료구조 - 지름길 정보 저장할 Road 객체 (지름길 시작 위치, 지름길 도착 위치, 지름길 길이) - 지름길 객체 정보 저장할 Road형 배열 - 최단 거리 저장할 int형 배열 . (시작점,도착점,거리)를 저장하는 Road를 생성한다. . Road형 배열에 객체 정보를 저장한다. . 0부터 다익스트라를 진행한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..

📖 문제 16395번: 파스칼의 삼각형 파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행 www.acmicpc.net 💡 풀이 방식 • DP . 2차원 배열을조합 식 nCr = n-1Cr-1 + n-1Cr 을 활용해 채운다. - 첫 번째 열에 있는 칸과, 행=열인 칸은 1로 초기화 dp[n][k] = dp[n-1][k-1] + dp[n-1][k] 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import java.util.*; import java.io.*; publi..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DP 1. 2차원 배열을 입력받는다. 2. 2차원 배열 dp를 초기화한다. - dp[0][0] = arr[0][0] - 맨 위쪽 줄은 arr 배열의 왼쪽 칸과 현재 칸의 값 中 큰 값으로 초기화 - 맨 왼쪽 줄은 arr 배열의 위쪽 칸과 현재 칸의 값 中 큰 값으로 초기화 3. 나머지 칸은 현재 칸의 위쪽과 왼쪽 中 더 작은 값을 구한다. 그리고 이 값과 현재 칸의 값을 비교해 둘 中 더 큰 값으로 현재 칸의 값을 갱신한다. (= 최댓값을 최소로) 🔺 코드 1 2 3 4 5 6..