본문 바로가기

Algorithm/DP8

[백준] 13398번 : 연속합 2 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net DP문제 이다. 연속된 수열의 최대합을 구하는 문제지만, 수열중 숫자 1개는 삭제 가능하다는 추가 조건이 있다. 따라서, 삭제 기회를 쓰는경우와 안쓰는 경우로 나눈 이차원 배열을 사용하였다. dp[i][0] : 0부터 i번째까지 존재하는 연속된 수열의 최대합 & 삭제 기회 남음 삭제 기회를 사용하면 안되기 때문에 i-1번째까지 최대합에 현재 값을 더한것과 현재값부터 다시 시작하는 경우 두가지 경우를 .. 2021. 11. 22.
[프로그래머스] N으로 표현 (JAVA) https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr import java.util.*; class Solution { int result=Integer.MAX_VALUE; int A; void solve(int n, int cur, int cnt){ if(cnt>8) return; if(cur==n) { result=Math.min(result,cnt); return; } int temp=A; for(int i=1; i 2021. 10. 16.
[백준] 구간 합 구하기 5 (C++) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net #include using namespace std; int N, M; int map[1025][1025]; int dp[1025][1025]; int main() { ios_base::sync_with_stdio(false); cout.tie(NULL);cin.tie(NULL); cin >> N >> M; for (int i = 1; i map[i][j.. 2021. 10. 8.
[백준] 1753번 : 최단경로 (C++, 다익스트라) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 우선순위 큐에 { 노드번호, 가중치 } 순서로 넣으면 정렬이 노드 번호가 작은 순서, 같으면 가중치가 작은 순서로 우선순위 큐가 작동하기 때문에 시간초과가 떴다. 따라서, { 가중치, 노드번호 } 순으로 넣어 해결하였다. #include #include #include using namespace std; int V, E,K; vector vec[20001]; int D.. 2021. 9. 17.
[프로그래머스] 정수 삼각형 (C++) https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr DP문제이다. 아래와 같은 삼각형이 있을때, 위에서 밑으로 내려가는 방향으로 2차원 dp배열을 통해 최대 누적합을 갱신시켜주었다. 그리고, 맨 아래에 있는 누적합 결과중 가장 큰 값을 출력해주었다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ↓ 7 10 15 18 16 15 20 25 20 19 24 30 27 25 24 => 제일 큰 누적합은 30 #include #include #include #include using n.. 2021. 9. 16.
[백준] 10164번 : 격자상의 경로 https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 전에 비슷한 경로의 수 구하는 문제를 풀었던 기억이 있어서 DP로 금방 구현하였다. 이 문제에서 핵심은 O로 표시된 좌표를 꼭 지나가야된다는 것이다. 만약, 다음과 같은 사진에서 8을 꼭 지나야 한다면, 8을 기준으로 왼쪽 밑 & 오른쪽 위 좌표들은 계산할 필요도 없고 누적 경로수 계산에 포함시키면 안된다. (Check 함수로 구현하였다.) 전체코드는 아래와 .. 2021. 9. 3.

티스토리툴바