-

S/W 엔지니어를 포기할 까 고민하게 만든 문제였다. 결국 많이 풀어봐야 할 것 같다,, DP문제를 풀 때, 습관적? 고정관념적으로 DP[n] = DP[n-1] + DP[n-2] 처럼 매우 1차원적으로 점진적으로 값이 (오른쪽으로) 쌓여간다는 생각을 하게된다. 이렇게 1차원 적으로 DP문제를 접근하면 절~~~ 대로 풀 수 없는 문제인 것 같다. 우선 이 문제를 풀기 위한 핵심은 1. 파일이 합쳐 지는 원리(계산)2. DP 점화식 세우기 1번 같은 경우 문제를 "정확히" 분석하지 않고 냅다 코딩부터 하니... 2번을 올바르게 세웠더라도 이 문제는 시간초과로 틀렸을 것이다. 여기서 가장 중요한 사실은 인접한 경우에만 합칠 수 있다는 것! 1~2개는 굳이 점화식이 필요없이 계산이 가능하다. 하지만 3장 부터가..

계단오르기 문제와 비슷한 DP 문제이다. 계단 오르기와 비슷하게 기준을 만들어야 한다. 기준없이 경우를 고려하면 점화식을 세우기 힘들다. 포도주 잔의 갯수를 1 부터 시작하여 차례대로 dp를 만들어 나간다. 1잔일 경우 당연히 dp[1] = a[1]; 이다. dp[2] = a[1] + a[2]; 가 된다. 3잔 부터는 기준이 필요.(3잔 이후로는 같은 원리가 적용됨) *연속된 세잔은 불가능 하다. 1. 마지막 잔을 마시지 않을 경우 dp[n] = dp[n-1]; 2. 마지막 잔을 마시는데 첫 번째 잔일 경우. dp[n] = dp[n-2] + a[n]; 3. 마지막 잔을 마시는데 두 번째 잔일 경우. dp[n] = dp[n-3] + a[n-1] + a[n]; 이렇게 경우를 나누어 주면 문제는 굉장히 쉽게 ..

처음 짜서 런타임에러 + 논리적 오류가 발생한 코드 #include #include using namespace std; int D[1001];int XY[1001][1001];int DP[1001]; int main(){ int T = 0, N = 1, K = 1, X, Y, W; cin >> T; while (T--){int ans = 0;cin >> N >> K;for (int i = 1; i > D[i];} for (int i = 1; i > X >> Y;XY[X][Y] = 1;}cin >> W; DP[1] = D[1];for (int i = 1; i N >> K; for (int j = 1; j > D[j];for (int j = 0; j < K; j++) {int x, y;//scanf("%d..

브루트포스로 풀릴것 같은데 왠지 시관초과가 날 것 같다. 꼭 다시 재귀방법으로 풀어보기로. 변수 정의를 잘 해야겠다. D[x] 를 "x를 1로 만드는데 필요한 최소한의 연산 횟수" 라고 정의한다면 문제가 쉬워진다. 코드:#include using namespace std; int D[1000001]; int main(){int X;cin >> X; D[1] = 0;D[2] = D[3] = 1;int temp = 0;for (int i = 4; i

점화식으로 바로 접근해서 헷갈리는 부분이 많았다. D[n] = Max(D[n-2),D(n-1) + S(n) 이런 형식을 가지고만 생각하면 풀기 너무 어려워진다. 경우의 수를 나누어야 한다. 제일 마지막 계단은 무조건 밟아야 하는 것과 세번 연속 오를 수 없다는 것을 기준으로 경우를 나눠야 한다. 두가지 경우로 나누어 생각. 즉, 점화식을 세울 때 O X O O --> D[n-3] + S[n-1] + S[n] // 전전전칸까의 최대값 + 전계단 + 마지막 계단 ? O X O --> D[n-2] + S[n] // 전전칸까지의 최대값 + 마지막 계단 코드: #include /*계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수..

DP 기초. 인덱스 문제 때문에 한참을 헷갈렸다. 특별한 알고리즘 없이 결국에 왼쪽으로 가느냐 오른쪽으로 가느냐 이부분 인덱싱 처리만 잘해주면 된다. 인덱스 계산이 가장 짜증난다나에겐... 코드: #include using namespace std; int arr[125251];int D[125251]; int MAX(int a, int b){return a > b ? a : b;}int height(int a){int tmp = 0;int ret = 0;for (int i = 1; i N;for (int i = 1; i arr[i];}D[1] = arr[1];for (int i = 2; i

틀렸는데 대충 로직은 맞다. 다시 짜기 귀찮음 + 예시 한개 통과하면 다른 것에서 실패. 즉, 새롭게 짜야하는데 그러기 싫기에 먼 훗날 다시 보는것으로,. 코드: #include #include using namespace std;int arr[50];int main(){int N, M, cnt = 0;cin >> N >> M;deque dq;for (int i = 0; i > arr[i];}int k = 0; while (M--){ int index;for (int i = 0; i < N; i++){if (dq[i] == arr[k]){index = i + 1;break;}} if (arr..

제출한 코드가 맞긴 하지만 뭔가 찝찝하다. 무분별하게 STL을 가져다 쓴 듯하다. 코드:#include #include #include #include #include using namespace std; int main(){ //pair p1;//p1 = make_pair(10, 20);int T = 0;cin >> T;while (T--){int N, M,cnt=1;cin >> N >> M;queue Q;vector V(N);for (int i = 0; i > get;V[i] = get;pair p;p = make_pair(i, get);Q.push(p);}sort(V.begin(), V.end());int index = N-1;while (true){if (..