아인스트라세의 SW 블로그

알고리즘 공부를 제대로 해보겠다고 다짐하고난 뒤의 나에게 코드포스는 꽤 괜찮은 공부법인듯 합니다.

온라인 컨테스트가 생각보다 자주 있고, (월 6회정도라고 합니다) 대회형식으로 2시간 집중해서 문제를 풀게 되며, 추후 컨테스트가 끝난 뒤 풀이도 제공합니다. (모든 컨테스트에 대하여 모두 제공하는지는 모르겠습니다.)

또 컨테스트가 끝난 뒤 채점을 하면, 어떤 테스트 케이스에서 틀렸는지, 테스트 케이스 값도 같이 보여줍니다.

알고리즘 공부하기에는 정말 좋은 사이트라고 생각합니다.

A번 문제는 방식을 하나하나 따라가면 되는 시뮬레이션 문제였습니다.

c장의 책을 매일 읽는데 처음에는 v0페이지씩 읽고, 다음날은 v0+a페이지를 읽고, 그다음날은 v0+a+a페이지를 읽고.. 이런식으로 읽는 페이지수에 가속도가 붙다가, 그 읽는 페이지 양의 한계는 v1페이지 입니다.

그리고 다음날 읽을 때는 전날 읽은 페이지 다음부터 읽는것이 아니라 마지막 l페이지 만큼은 다시 복습을 한다고 합니다.

이러할 때 c페이지의 책을 모두 읽는데 걸리는 날 수를 구하는 문제입니다.

아래는 코드입니다.

#include <iostream>

using namespace std;

int main() {
	int c, v0, v1, a, l;
	int current_page = 0;
	int iteration = 0;
	cin >> c >> v0 >> v1 >> a >> l;

	while(true) {
		int increment = v0 + iteration * a;
		if (increment > v1) increment = v1;
		iteration++;
		current_page += increment;
		if (current_page >= c) break;
		current_page -= l;
	}
	cout << iteration << endl;
}

B번 문제는 기하문제인데, 정 n각형에서 각도 a를 구할 때 각 a와 가장 근사한 값을 가진 각도를 나타내는 꼭지점 번호를 구하는 문제입니다.

정 n각형의 그림은 다음 페이지에서 참조했습니다.

그림을 그려보면 n각형에서 나타나는 각도에 패턴이 있는데, 

5각형의 예를 들면, 저기 보이는 검정색 각도(interior angle)이 k라고 하고, 빨간색 각도를 theta라고 한다면

나타날 수 있는 각도는 다음과 같습니다.

v1 v2 v3 = k

v1 v2 v4 = k - theta

v1 v2 v5 = k - theta - theta

n의 수가 커지면 저 k - theta - theta - theta ... - theta 이런식의 경우도 나타나겠죠?

k와 theta는 n에 관한 수식으로 나타낼 수 있습니다.

위 식을 이용해서 적용하면 답을 구할 수 있습니다.

아래는 코드입니다.

#include <iostream>

using namespace std;

double ABS(double x) {
	return x*x;
}

int main() {
	int n, a;
	double k, theta;
	int ans = 3;
	double error = 9999999;
	
	cin >> n >> a;
	k = 180 - (((double)360)/n);
	theta = (((double)180)/n);
	
	double candidate = k;
	error = ABS(candidate - a);
	for (int v3 = 3; v3 <= n; v3++) {
		double cur_err = ABS(candidate - a);
		if (cur_err <= error) {
			ans = v3;
			error = cur_err;
		}
		candidate -= theta;
	}
	cout << "1 2 " << ans << endl;
}

아직은 내공이 부족해서 두 문제 밖에 풀지 못했지만, 꾸준히 풀어서 좀 더 높은 레이팅을 목표로 해보겠습니다.

https://www.acmicpc.net/problem/2670

첫번째 포스팅입니다.

한국정보올림피아드 1996년도 중등부 1번문제 연속부분최대곱 문제를 풀어봤습니다.

흔하디 흔한 dp(dynamic programming)으로 풀었습니다.

dp[i]는 i번째 수열에서 끝나는 부분수열의 최대곱을 저장합니다.

가령 arr이 원래 수열이라고 하면

dp[0]은 arr[0]

dp[1]는 arr[0] * arr[1]

dp[2]은 arr[0] * arr[1] * arr[2]

dp[3]은 arr[0] * arr[1] * arr[2] * arr[3]

dp[4]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4]

dp[5]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4] * arr[5]

dp[6]은 arr[0] * arr[1] * arr[2] * arr[3] * arr[4] * arr[5]

dp[7]은 arr[7]

이 됩니다.

dp[7]의 경우를 제외하고 항상 더 곱하는것이 좋은 결과를 가져오는데, dp[6]의 경우 1보다 작으므로, dp[7]에서는 이전 앞의 누적 곱을 제외하고 본인만 가져가는것이 이득이므로 dp[7] = arr[7]이 됩니다.

출력 시, 포맷 스트링으로 %.3lf를 사용하면 소수점 4번째 자리에서 자동 반올림된 값이 나타나는 것을 처음 알았네요.

반올림 된 값으로 출력만 할 경우 유용할 것 같습니다.

#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef double vt;

int N;
vector<vt> arr;
vector<vt> dp;

int main() {
	cin >> N;
	
	arr.reserve(N);
	dp.reserve(N+1);
	for (int i=0; i < N; i++) {
		vt val;
		cin >> val;
		arr.push_back(val);
	}
	dp[0] = arr[0];
	for (int i=1; i <= N; i++) {
		if (dp[i-1] > 1) {
			dp[i] = dp[i-1] * arr[i];
		} else {
			dp[i] = arr[i];
		}
	}
	vt max_val = -987654321;
	for (int i=0; i < N; i++) {
		max_val = max(max_val, dp[i]);
	}
	printf("%.3lf\n", max_val);
	
}