#include <iostream> using namespace std; class Stair { private: int Stairs[3]; int UpMost[3] = { 0,0,0 }; int UpLeast[3] = { 0,0,0 }; int Num; public: Stair(int n); void Descend(); }; Stair::Stair(int n) { this->Num = n; } void Stair::Descend() { int A, B, C, D; cin >> this->Stairs[0] >> this->Stairs[1] >> this->Stairs[2]; this->UpMost[0] = this->Stairs[0]; this->UpMost[1] = this->Stairs[1]; this->UpMost[2] = this->Stairs[2]; this->UpLeast[0] = this->Stairs[0]; this->UpLeast[1] = this->Stairs[1]; this->UpLeast[2] = this->Stairs[2]; for(int i = 1; i < this->Num; i++) { cin >> this->Stairs[0] >> this->Stairs[1] >> this->Stairs[2]; A = (this->UpMost[0] + this->Stairs[0]) < (this->UpMost[1] + this->Stairs[0]) ? this->UpMost[1] + this->Stairs[0] : this->UpMost[0] + this->Stairs[0]; B = (this->UpMost[0] + this->Stairs[1]) < (this->UpMost[1] + this->Stairs[1]) ? this->UpMost[1] + this->Stairs[1] : this->UpMost[0] + this->Stairs[1]; C = B < (this->UpMost[2] + this->Stairs[1]) ? (this->UpMost[2] + this->Stairs[1]) : B; D = (this->UpMost[2] + this->Stairs[2]) < (this->UpMost[1] + this->Stairs[2]) ? this->UpMost[1] + this->Stairs[2] : this->UpMost[2] + this->Stairs[2]; this->UpMost[0] = A; this->UpMost[1] = C; this->UpMost[2] = D; A = (this->UpLeast[0] + this->Stairs[0]) > (this->UpLeast[1] + this->Stairs[0]) ? this->UpLeast[1] + this->Stairs[0] : this->UpLeast[0] + this->Stairs[0]; B = (this->UpLeast[0] + this->Stairs[1]) > (this->UpLeast[1] + this->Stairs[1]) ? this->UpLeast[1] + this->Stairs[1] : this->UpLeast[0] + this->Stairs[1]; C = B > (this->UpLeast[2] + this->Stairs[1]) ? (this->UpLeast[2] + this->Stairs[1]) : B; D = (this->UpLeast[2] + this->Stairs[2]) > (this->UpLeast[1] + this->Stairs[2]) ? this->UpLeast[1] + this->Stairs[2] : this->UpLeast[2] + this->Stairs[2]; this->UpLeast[0] = A; this->UpLeast[1] = C; this->UpLeast[2] = D; } cout << ((this->UpMost[0] < this->UpMost[1] ? this->UpMost[1] : this->UpMost[0]) < this->UpMost[2] ? this->UpMost[2] : (this->UpMost[0] < this->UpMost[1] ? this->UpMost[1] : this->UpMost[0])) << " "; cout << ((this->UpLeast[0] > this->UpLeast[1] ? this->UpLeast[1] : this->UpLeast[0]) > this->UpLeast[2] ? this->UpLeast[2] : (this->UpLeast[0] > this->UpLeast[1] ? this->UpLeast[1] : this->UpLeast[0])); } int main() { int Num; cin >> Num; Stair S(Num); S.Descend(); return 0; }
1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만 ! DP를 사용해서 풀 수 없는 문제이다 . 하지만 DP가 쓰이긴 한다! 수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다. 왜 곱셈의 역원을 구해야하는가? N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문! 곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면 p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요. 분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다. DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다. 그러므로 총 시간 소요는 O(N+LogP) long long BinomialCoefficient :: GetNum ( int N , int K ) { this - > Factorial [ 1 ] = 1 ; for ( int i = 2 ; i < = 4000000 ; i + + ) this - > Factorial [ i ] = ( this - > Factorial [ i - 1 ] * i ) % P ; this - > Invert [ 4000000 ] = this - > Pow_DC ( this - > Factorial [ 4000000 ] , P - 2 ) ; for ( int i = 4000000 - 1 ; i > 0 ; i - - ) this - > Invert [ i ] = ( this - > Invert [ i + 1 ] * ( i + 1 ) ) % P ; if ( N = = K | | K = ...
댓글
댓글 쓰기