분류 전체보기52 1912. 연속합 1. 시간 초과된 풀이 더보기 문제풀이 : 1) DP[] 배열에 choose 개의 연속된 수의 합을 저장했다. 그리고 N[] 배열에 입력받은 수열을 저장했다. 2) DP[] 배열은 choose 의 값에 따라 저장되는 값이 달라진다. 3) choose = 1 일 때의 DP[] 배열은 N[] 배열과 동일하다. DP[i] = N[i] 4) choose = 2 일 때의 DP[] 배열은 DP[i] = N[i] + N[i+1] 이다. 즉, DP[i] = (choose = 1 일 때의 DP[i]) + N[i+1] 5) choose = 3 일 때의 DP[] 배열은 DP[i] = N[i] + N[i+1] + N[i+2] 이다. 즉, DP[i] = (choose = 2 일 때의 DP[i]) + N[i+2] 6) 정리하자면.. 2022. 8. 8. 1463. 1로 만들기 1. 해결방법 Dynamic Programming 문제이다. DP[n] 의 의미는 n을 1로 만들 수 있는 최소 연산 횟수이다. DP[0] = DP[1] = 0 ☞ 0은 범위 밖이고, 1을 1로 만들기 위한 연산은 0번이기 때문이다. DP[2] = 1, DP[3] = 1 그렇다면 DP[4] 는 ??? DP[4] 는 N-1 로 3으로 만들고(1회) + DP[3] 이다. 즉, DP[N] = DP[N-1] + 1 또는 DP[N] = DP[N/2] + 1 또는 DP[N] = DP[N/3] + 1 이다. 2. Solution // Dynamic Programming #include #include #define MAX 1000000 + 1 #define endl "\n" using namespace std; in.. 2022. 8. 5. 1149. RGB거리 1. 해결방법 Dynamic Programming DP 문제의 해결방법은 "큰 문제를 작은 문제로 나누기이다. 즉, 1)DP[][] 값 모두 구하고 2) answer 찾기"이다. 2. Solution // Dynamic Programming #include #define MAX 1000 + 1 #define endl "\n" using namespace std; int N, answer; int MAP[MAX][3]; int DP[MAX][3]; int Min(int A, int B) {if(A > N; for(int i = 1; i > MAP[i][j]; } } // 초기화 DP[0][0] = DP[0][1] = DP[0.. 2022. 8. 5. 1003. 피보나치 함수 1. 시간초과된 풀이 더보기 #include #include #define endl "\n" using namespace std; int T, N; vector testCase; int cnt_zero = 0, cnt_one = 0; void Input() { cin >> T; for(int i = 0; i > N; testCase.push_back(N); } } int fibonacci(int n) { if(n == 0) { cnt_zero += 1; return 0; } else if(n == 1) { cnt_one += 1; return 0; } else{ return fibonacci(n-1) + fibonacci(n-2); } } void Solution() { f.. 2022. 8. 2. 이전 1 2 3 4 5 6 7 ··· 13 다음
