백준 24533 - 결합 (수학적 귀납법)

백준 24533

 

문제 풀이

30만개의 물질을 가지고 있기 때문에 N혹은 NlogN의 시간정도에 계산을 해내야 했다.

이런 문제는 일반적으로 그리디하게 규칙을 찾아 우선순위 큐에서 뽑아 NlogN으로 하거나, DP로 무언가 기억해 놓고 N의 시간에 해결을 하는것이 국룰인데, 아무리 생각해도 방법이 보이지 않았다.

 

어떤 방식으로 합쳐야지 가장 큰 에너지값을 얻을수 있을지 잘 떠오르지 않아, 임의로 4개의 테스트케이스를 만들어 손으로 써가며 모든 결합하는 경우의 수를 계산하면서 통찰을 얻으려고했다.

실제로 계산을 해보니 결합순서와 관계없이 에너지량이 항상 같은것을 확인하였다.

 

하지만 어떻게 계산을 하던 에너지량이 같은것은 증명을 통해 보였어야 하는데, 수학적인 역량이 아쉬워서 문제를 풀 당시에는 증명하지 못했다. 그래서 문제풀이 이후 수학적 귀납법을 통한 증명을 공부하고 이 문제에 대해서도 증명을 해 보았다.

 

답안 :

#include <iostream>

using namespace std;

int N;

int main()
{
	cin >> N;
	long long x = 0;
	long long y = 0;
	long long E = 0;
	for(int i = 0; i < N; i++)
	{
		long long a, b;
		cin >> a >> b;
		E += a * y + b * x;
		x += a;
		y += b;
	}
	cout << E << endl;
}

 

수학적 귀납법

수학적 귀납법의 기본적인 아이디어는 다음과 같다.

 

어떤 가정을 한다.

1일때 성립함을 확인한다.

2일때 성립함을 확인한다.

3일때 성립함을 확인한다.

.

.

 

모두 되겠네 ?

 

하지만 위와같이 하면 모든 경우를 확인하지 않으면 모든경우가 성립함을 보장할 수 없으므로 다음과 같이 일반화 할 수 있다.

 

어떤 가정을 한다.

초기상태일때 성립함을 확인한다.(보통 1)

 

k일때 성립한다고 가정한다.

k+1일때도 성립하는지 확인한다.

만약 성립한다면 초기상태 다음값(보통 2)가 성립하고

2의 다음값인 3도 성립한다.

3의 다음값인 4도 성립한다.

.

.

.

모두 성립한다.

 

이렇게 꼬리에 꼬리를 물며 성립이 되는것을 일반화 할 수 있다.

 

아래는 유투부 수악중독 선생님의 강의를 들으며 정리한 내용이다.

 

이번 문제에서의 수학적귀납법 증명

 

출처:

https://www.youtube.com/watch?v=fRiuMn6_fBA