궤도

문제 풀이 myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 단순히 수열의 길이만 구하던 위 문제에서 응용된 문제이다. 처음에는 그냥 length가 늘어날 때마다 dp 배열을 그대로 복사하면 되는거 아닌가? 했다가 반례를 만났다. 10 3 7 4 1 8 이 경우 11053에서 작성한 내 코드 기준 dp를 그대로 복사해오면 1 4 8이란 결과가 나온다. 딱봐도 말도 안된다는 것을 알 수 있다. 그래서 배열의 ..

문제 풀이 문제의 조건에 따르면 스티커를 뗼 수 있는 방법은 OXOX XOXO XOXO OXOX 이렇게 지그재그로 떼는 방법밖에 없다. XXOX XXXX 만약 이 동그라미로 표시한 스티커를 떼고 싶다고 하자. 그럼 그 이전까지의 스티커는 어떤 상태여야 할까? OXOX XXOX XOXX OXXX 이런 모습이어야 할 것이다. 그니까 연속으로 떼거나, 한 칸 건너뛰고 떼거나의 방법이 있는 것이다. 점화식을 작성하면 dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + cost[0][i]; dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + cost[1][i]; 이렇게 된다. dp[0][i]와 dp[1][i]중 더 큰 값이 스티커 점수의 최댓값이다. 소스코..

문제 풀이 myunji.tistory.com/318?category=1154147 [백준] 15988번 : 1, 2, 3 더하기 3 문제 풀이 myunji.tistory.com/298 [백준] 9095번 : 1, 2, 3 더하기 문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호 myunji.tistory.com 이 문제에서 숫자의 연속 등장을 제외해야 하는 문제이다. 숫자의 연속 등장을 제외하기 위해선 마지막에 등장한 숫자가 무엇인지 저장해야 한다. 1, 2, 3 더하기니까 마지막에 등장할 수 있는 숫자 역시 1, 2, 3이다. dp[i][j]에 숫자 i를 1, 2, 3의 합으로 나타낸 경우 중 j+1로 끝나는 것..

문제 풀이 myunji.tistory.com/298 [백준] 9095번 : 1, 2, 3 더하기 문제 풀이 dp로 풀면 더 빠르겠지만 난 그냥 백트래킹으로 풀었다. 3~1을 빼서 음수가 되지 않으면 계속 빼주면서 백트래킹 재귀 함수를 호출한다. 소스코드 #include using namespace std; int cnt; void backtr myunji.tistory.com 이 문제를 풀 때는 n이 11보다 작기 때문에 재귀함수로 풀 수 있었다. 하지만 이번엔 n이 1,000,000까지 들어올 수 있기 때문에 재귀함수로 풀면 시간이 너무 오래 걸릴 것이다. 그래서 동적계획법(dp)로 풀어야 한다. 특정 수 i에 대해 i를 1, 2, 3의 합으로 나타내는 방법은 다음과 같다. (i-1을 1, 2, 3의 ..