sw 두 정수 쌍들의 합

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbHl3F6AKMDFAV0&categoryId=AWbHl3F6AKMDFAV0&categoryType=CODE

SW Expert Academy

f(x y) f{x-1,y)+f(x,y-1)
f(1 0)=1
f(0 1)=1
f(0 0)=1
f(1 1)=f(0 1)+f(1 0)=1+1=2
f(1 2)=f(0 2)+f(1 1)=1+1+1=3
f(1 3)=f(03)+ f(1 2)=1+1+1+1=4
f(2 1)=f(1,1)+f(2 0)=1+1+1=3
f(2 2)=f(1 2)+f(2 1)=3+3=6
f(2 3)=f(1 3)+f(2 2)=4+6=10
f(2 4)=f(1 4)+f(2 3)=5+10=15
3 3 2 3  3 2
다 구해놓기는 힘들것같다.. c의 범위가 10^18이기 때문에

그때 그때 함수를 불러서 호출하는게 나을long long으로 해야할듯

값을 기억해놔야 하니까 이것도 Dynamic programming이라고 할 수 있는건가 

우선 일차방정식 구하는 방법

#include<iostream>

using namespace std;
int sum;
int arr[100][100];

int func(int x1, int y1) {
	int sum1;
	if (x1 == 0 || y1 == 0)
		arr[x1][y1] = 1;
	else {
		for (int i = 0;i <= x1;i++) {
			for (int j = 0;j <= y1;j++) {
				if (i == 0 || j == 0)
					arr[i][j] = 1;
				else
					arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
			}
		}
	}
	sum1 = arr[x1][y1];
	return sum1;

}
int main(int argc, char** argv) {
	int test_case;
	int T;
	int a, b, c;
	int result;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case) {
		sum = 0;
		cin >> a >> b >> c;
		for (int x = 0;x <= (c/a);x++) {
			for (int y = 0;y <= (c/b);y++) {
				result = a*x + b*y;
				if (result == c)
					sum += func(x, y);
			}
		}
		cout << "#" << test_case % 1000000007 << " " << sum << endl;
	}
	return 0;
}

먼저 코드는 짜자마자 한번에 테스트 케이스를 다 통과했다.

코드는 정말 알맞게 짰는데 문제는 시간..

우선 이렇게 하면 답은 나오지만 30개 테스트를 1초 안에 통과할 수가 없다..

그래서 테스트 4개인가 밖에 못함..

제출이력을 보던중

다른분이 한걸 봤는데 그분은 런타임 에러가 나서 Fail이긴 하지만 실행시간이 내가 4개를 하는동안 1000ms인 반면

그분은 8개를 하는 동안 69ms였다.

진심 충격받음

그분 코드를 봤는데 map과 memoization을 활용하신 것 같았다.........

내일은 map vector memoization iter등등 시간을 줄일 수 있는 c++명령어/라이브러리를 공부해야 할 것 같다.