Little Jay

Prefix Sum문제. 문제에서 정확히 뭘 출력하라고 하는지만 파악하면 쉽게 풀 수 있다. #include #define endl '\n' using namespace std; int dp[1025][1025]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; int x1, y1, x2, y2; cin >> n >> m; for (int i = 1; i dp[i][j]; for (int i = 1; i y1 >> x2 >> y2; cout

DP가 하도 어려워서 요새 DP를 집중적으로 공부하고 있다. 그 와중에 조금 어이없는(?) 문제를 발견해서 풀이를 올리고자 한다. 위 문제는 어떤 실수 형태의 배열에서 연속되는 구간의 곱의 최대값을 출력하는 문제이다. 이를 간단하게 구성을 construct해보면 어떤 배열이 자기 자신으로 초기화 된 후에, 그 0번 인덱스의 것을 제외하고 1번 인덱스부터 자기 자신과 그 전에 있는 것의 곱의 대소 비교를 통해서 누적곱을 구할 수 있다. 이렇게 업데이트 시켜 주면서 최대값을 찾아주면 정답인데, C++를 하는 사람들은 당연히 setprecision 메서드를 사용했을 것이다. 문제는 이렇게 하면 정답이 아니다. 문제에서 요구한 것은 어떤 값들이 들어와도 소수 3번째 자리수까지 출력하는 것이다. 정수값을 setp..

문제를 잘 곱씹어보면 아이디어가 하나 떠올랐는데, 백준 문제의 '가장 긴 증가하는 부분 수열' 이 떠올랐다. 생각해보면 이 아이디어가 Correct하게 맞아떨어지는데, 이는 해당 구간에서 오름차순으로 증가하는 수열이 결국 이 문제의 상자와 같기 때문이다. #include #define endl '\n' using namespace std; int n; int dp[1001]; int arr[1001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i > arr[i]; } int ans = -1; for (int i = 1; i

이차원 배열을 사용해야하는 dp문제 #include #define endl '\n' using namespace std; int n, a, b; int minMul[501][501]; vector v; int matOrder(vector& v, int n) { for (int i = 1; i > a >> b; if (i == n - 1) { v.push_back(a); v.push_back(b); } else { v.push_back(a); } } cout

피보나치 수에 대한 문제입니다. 피보나치 수는 아래와 같이 정의됩니다. f(1) = 1 f(2) = 2 f(3) = f(1) + f(2) = 1 + 2 = 3 f(4) = f(2) + f(3) = 2 + 3 = 5 f(5) = f(3) + f(4) = 3 + 5 = 8 ... f(n) = f(n-2) + f(n-1), n>=3 a와 b라는 두 수가 주어져 있을 때 두 수 사이에는 몇 개의 피보나치 수가 있을까요? 예를 들어 10과 100 사이에는 총 5개(13, 21, 34, 55, 89)의 피보나치 수가 있고 모두 더한 값은 212입니다. 12345678999과 99987654321 사이에도 몇 개의 피보나치 수가 있습니다. 이 구간 내의 모든 피보나치 수를 더한 값이 기념품을 받을 수 있는 열쇠입니다..

ascii 코드를 이용해서 잘 변환시키는게 중요했던 문제 처음에 알파벳 변환은 'A'의 아스키 값인 65를 빼주면 되고, 숫자를 임시적으로 문자열로 저장했을 때, 이를 다시 숫자로 변환할때는 0의 아스키 값인 48을 빼주면 된다. #include #define endl '\n' using namespace std; int alphabet[] = { 3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 1 }; string s1, s2; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> s1; cin >> s2; string..

dp 시작 #include #define endl '\n' using namespace std; long long dp[85]; int n; int main() { cin >> n; dp[0] = 0; dp[1] = 1; for (int i = 2; i

간단한 파스칼 삼각형 구하는 문제 #include #include using namespace std; int bridges[31][31]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); for (int i = 1; i t; while (t--) { int n, m; cin >> n >> m; cout

DP가 정말 어렵다 점화식을 어떻게 구현할 것인가의 문제인데, 이 부분에서 훈련이 더 필요할 것 같다. #include #include using namespace std; int house[1005][3]; int color[1005][3]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 0; i > house[i][0] >> house[i][1] >> house[i][2]; } color[0][0] = house[0][0]; color[0][1] = house[0][1]; color[0][2] = house[0][2]; for (int i = 1; i < n; i++)..

DP를 사용하는 문제 DP의 합과 입력받은 arr의 숫자를 잘 비교하면 되는 것 같다. #include #include using namespace std; int arr[100001]{ 0, }; int dp[100001]{ 0, }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i > arr[i]; } dp[1] = arr[1]; int result = dp[1]; for (int i = 2; i