https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 1. DP 배열 만들기 Dp 문제를 풀기 위해서 가장 먼저 해야할 일은 dp 배열을 정의하는 것이다. 이 문제에서는 dp[a][b]는 a,b 까지의 누적 합을 뜻한다. 예를들어 dp[2][2] 라고 하면 파란 영역의 합을 뜻한다. dp[3][4]는 위 그림의 파란 영역의 합을 뜻한다. dp문제는 점화식을 이용하여 풀어야 한다. 이 문제는 비교적 점화식이 ..
다이나믹 프로그래밍 문제이다. 실버 문제라서 그런지 식이 바로 떠올라서 바로 풀었다. 가장 i =1 부터 i+1 , i *2 , i*3 을 하나씩 계산해 주면 된다. 사실 3번 틀렸는데 이유가 dp[1] = 1이 아니라 dp[1] =0 이다. dp[1] =1이라고 하면 100% 까지 가서 틀렸습니다가 뜬다. #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 typedef long long ll; using namespace std; int num; int cnt=0; int dp[1000005]; int main() { cin >> num; for (int i = 1; i
dp 로 풀리는 문제이다. [1,1] 에서 최대 이동 거리 D 이내에 갈 수 있는 곳을 모두 계산하는 방식으로 풀었다. 예를들어 아래와 같은 input이 있을 때 4 3 2 3 -5 4 2 0 0 1 -3 1 -2 9 1 [1,1]에서 갈 수 있는곳은 [2,1] [3,1] [2,2]이다. 그럼 [1,1]을 거쳐서 [2,1] [3,1] [2,2]에 갈때의 점수를 계산해서 원래의 값보다 더 크면 값을 바꿔준다. #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321999 typedef long long ll; using namespace std; int N, M, D; vector < ..
#include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; int row[3001][3001]; int col[3001][3001]; int dp[3001][3001]; int board[3001][3001]; int N, M; int main() { cin >> N >>M; FASTIO; //입력 string str =""; for (int i = 0; i > str; for (int j = 0; j < M; j++) { if (str[j] == 'B') { board[i][j] = 0; } else if(str[j]..
한번 틀려서 이유를 찾고자 조금 구글링을 한 문제였다. 구글링 해보니 예전에는 내리 갈굼 문제였는데, 지금은 칭찬하는걸로 내용이 바꼈다 ㅋㅋ 조금 귀엽게 바꾼것 같다 dp 를이용하여 풀었다. 그래프는 parent[] 배열을 이용하여 표현하였다. #include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; int now[100001]; int dp[100001]; int parent[100001]; int N, M; int main() { cin >> N >>M; //직원관계 받기 int a, b, c; for (int i = 0; i a; parent..
