굳건하게

문제 : https://www.acmicpc.net/problem/13328

[알고리즘풀이]

최대 call 횟수 d 와 시간 t 초가 주어졌을 때,

F(N) : Number of calls at time N ( N초에서 호출 횟수) 라고 정의하자.

그러면, 다음과 같은 점화식이 성립한다.

피보나치의 변형꼴로 F(t)를 구하기 위해서는 위의 점화식을 이용해야 한다.

점화식을 구하는 것도 어려웠는데, t 가 최대 20억까지 입력이 들어오므로, 단순히 반복문을 통해 F(t) 를 구하면 안 된다.

따라서, 행렬을 이용해서 F(t) 를 구해야 한다.

위의 점화식을 이용해 다음과 같은 행렬 곱셈이 성립함을 알아낼 수 있다.

이 연산을 반복하면 다음과 같은 행렬식을 얻어낼 수 있다.

즉, 행렬 A의 ( t - d ) 제곱을 구하면, F(t) 를 구할 수 있다.

이때, 행렬 A의 ( t - d ) 제곱은 메모리제이션을 이용해

다음과 같이 A의 2^n 승을 구해놓고, A의 2^n 승을 이용해 A의 ( t - d ) 제곱을 구할 수 있다.

#include<iostream>
#include<cmath>

using namespace std;

#define mod 31991
int d, t, list[51];

int map[33][50][50];
int answer[50][50];
int tanswer[50][50];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> d >> t;
	for (int i = 1; i <= d; i++)
		list[i] = (long long)pow(2, i - 1) % mod;
	if (t <= d){
		cout << list[t];
		return 0;
	}
	for (int i = 0; i < d; i++) {
		for (int j = 0; j < d; j++) {
			if (i == 0)
				map[0][i][j] = 1;
			else if (i == j + 1)
				map[0][i][j] = 1;
		}
	}

	int b = t - d;
	for (int i = 0; i < d; i++)
		for (int j = 0; j < d; j++)
			if (i == j)
				answer[i][j] = 1;
	int l;
	for (l = 0; ; l++)
		if ((long long)(pow(2, l)) > b)
			break;
	l--;
	for (int i = 1; i <= l; i++) {
		for (int j = 0; j < d; j++) {
			for (int k = 0; k < d; k++) {
				int temp = 0;
				for (int m = 0; m < d; m++) {
					temp += (map[i - 1][j][m] * map[i - 1][m][k]) % mod;
				}
				map[i][j][k] = temp % mod;
			}
		}
	}
	while (b) {
		int l;
		for (l = 0; ; l++) {
			if ((long long)(pow(2, l)) > b)
				break;
		}
		l--;
		for (int i = 0; i < d; i++) {
			for (int j = 0; j < d; j++) {
				int temp = 0;
				for (int m = 0; m < d; m++) {
					temp += (answer[i][m] * map[l][m][j]) % mod;
				}
				tanswer[i][j] = temp % mod;
			}
		}
		for (int i = 0; i < d; i++)
			for (int j = 0; j < d; j++)
				answer[i][j] = tanswer[i][j];
		b -= (long long)pow(2, l);

	}
	int k = 0;
	for (int i = 1; i <= d; i++) {
		k += (answer[0][i - 1] * list[d + 1 - i]) % mod;
		k = k % mod;
	}
	cout << k % mod;
}

푸는데 정말 애먹은 문제로, 점화식을 끌어내는 과정 + 점화식을 이용해 행렬 계산을 하는 과정까지

전부 다 어려웠던 문제입니다.

문제 : https://www.acmicpc.net/problem/13333

[알고리즘풀이]

1번 조건 : k 보다 크거나 같은 숫자를 k 개 뽑을 수 있어야한다.

2번 조건 : k 보다 작거나 같은 숫자를 n - k 개 뽑을 수 있어야 한다.

1번 조건에 의해 Q-Index는 최대 N이므로, N부터 역으로 순회하며 조건을 만족하는 Q-Index를 찾는다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, nl[1000];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> nl[i];
	}
	for (int i = n; i >= 0; i--) {
		// i 가 Q-Index
        int count = 0;
        for (int j = 0; j < n; j++){
        	if(nl[j] >= i)
            	count++;
        }
        if(count >= i){
        	cout << i;
        	return 0;    
        }
	}
}

문제 : https://www.acmicpc.net/problem/13335

[알고리즘풀이]

단순 구현 문제로, 시간 초마다 대기 중인 차를 다리 위로 보낼 수 있으면 올리고, 아니면 다리 위에 있는 차들만 앞으로 한 칸씩 전진하면 된다.

#include<iostream>
#include<algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, w, L, nl[1010] = {}, wl[2000] = {};
	cin >> n >> w >> L;
	for (int i = 0; i < n; i++)
		cin >> nl[i];
	
	int t = 1, cW = nl[0], s = 0, l = 1, c = 0;
	wl[0] = 1;

	while (t++) {
		// 다리위에있는애들 한 칸씩 전진
		for (int i = s; i < n; i++) {
			if (0 < wl[i] && wl[i] <= w){
				wl[i]++;
				if (wl[i] == w + 1){
					cW -= nl[i];
					wl[i] = 0;
					s++;
					c++;
				}
			}
		}
		// 새로운 애들을 다리 위로 올리자.
		if (cW + nl[l] <= L) {
			cW += nl[l];
			wl[l] = 1;
			l++;
		}
		if (c == n) {
			cout << t;
			break;
		}
	}

}

문제 : https://www.acmicpc.net/problem/8912

[알고리즘풀이]

Input 크기가 작아서 단순 구현하면 되는 문제다.

#include<iostream>

using namespace std;
int list[1000];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	int test_case;
    cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		int ninput;
        cin >> ninput;
		int total = 0;
		for (int j = 0; j < ninput; j++){
            cin >> list[j];
			for (int k = 0; k < j; k++) {
				if (list[k] <= list[j])
					total++;
			}
		}
        cout << total << '\n';
	}
}