백준

수열에서 N 위치까지의 원소의 합의 최대값을 구한다고 했다. 대신, 연속해서 3번이상 원소를 선택할 수 없다. 그렇다면, 합의 최대값을 MaxSumUntil[N] 이라고 한다면, 경우의 수를 다음과 같이 나눌 수 있다. 1. N번째 숫자를 고르지 않는 경우. 이 경우 MaxSumUntil[N] 은 MaxSumUntil[N - 1] 을 그대로 따라가게 된다. 2. N번째 숫자를 고르고, N - 1번째 숫자도 고르는 경우. 이 경우 N - 2번째 숫자는 고를 수 없다. 따라서 MaxSumUntil[N-3] + Element[N-1] + Element[N] 이 된다. 3. N번째 숫자를 고르고, N - 1번째 숫자를 고르지 않는 경우. 이 경우 MaxSumUntil[N-2] + Element[N] 이 된다. ..

N자리 계단수에 대해 끝자리가 1 - N-1자리 계단수의 끝자리가 0,2 끝자리가 2 - N-1자리 계단수의 끝자리가 1,3 끝자리가 3 - N-1자리 계단수의 끝자리가 2,4 끝자리가 4 - N-1자리 계단수의 끝자리가 3,5 끝자리가 5 - N-1자리 계단수의 끝자리가 4,6 끝자리가 6 - N-1자리 계단수의 끝자리가 5,7 끝자리가 7 - N-1자리 계단수의 끝자리가 6,8 끝자리가 8 - N-1자리 계단수의 끝자리가 7,9 끝자리가 9 - N-1자리 계단수의 끝자리가 8 끝자리가 0 - N-1자리 계단수의 끝자리가 1 모듈러 연산은 합에대한 분배법칙이 성립함에 유의하면 쉽게 풀어낼 수 있는 문제이다. #include unsigned long long LastNumberCounts[101][10]..

매우 간단한 문제이다. 나눗셈을 하는것이 무조건 이득이다. 75를 예로 들어보자 75 는 2^3 * 3 ^ 2 + 3 이다. 결국 몇으로 나눌지가 문제이다 이것을 재귀적으로 분기 할 수 있도록 식을 구성한다. 반복되는것이 있을 수 있으므로 메모리에 저장해둔다. #include #include #include int Memoization[1000001] = { 0 , }; int RecCalc(int Number) { if (Number < 2) return 0; int Select2 = 0; int Select3 = 0; if (0 != Memoization[Number]) return Memoization[Number]; if (0 != Memoization[Number / 3]) Select3 = M..

어떠한 인덱스 N에 도착하기 위한 경우의 수는 두가지 밖에 없다. 두칸 전에서 두칸을 뛰어 오르던지, 한칸전에서 한칸을 뛰어 오르던지. 근데 두칸을 올라서 굳이 한칸을 빼먹어야 될 일은 없다. 그래서 무조건 한칸씩 계속 오르면 최대값이다. 다 올라간게 무조건 최대값이다. 이건 문제가 되질 않는다. 그래서 문제에선 세칸이 연속되면 안된다는 조건을 건다. 두칸전에서 두칸을 뛰어 오르는 경우를 생각해보자. 이건 단순히 N - 2 번째 칸까지의 최대값에서, N 칸을 밟은 거다. 두칸을 올라온 거니 따로 제약사항이 없다.MAX(N) = MAX(N-2) + COST(N)이 나온다. 한칸전에서 한칸을 뛰어 오르는 경우를 생각해보자. 여긴 조건이 있다.따라서 패턴을 강제시킨다. N - 1 번째 칸에서 한칸을 뛰어 올랐..