Codetesing의 코딩공부

DP를 사용해서 2차원 배열의 구간합을 구하는 문제이다.

먼저 각 row 별로 col이 1에서부터 index 까지의 구간합을 구한다.

(x1, y1) (x2, y2) 가 입력되면 구한 구간합의 차를 이용하여 (x1, y1) (x1, y2) 를 구하여 x1 부터 x2 까지 반복하면 된다.

문제링크 :  11660번: 구간 합 구하기 5 (acmicpc.net)

#include <iostream>
#include <vector>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, M;
	cin >> N >> M;

	vector<vector<int>> map(N + 1, vector<int>(N + 1, 0));
	vector<vector<int>> sum(N + 1, vector<int>(N + 1, 0));

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			sum[i][j] = sum[i][j - 1] + map[i][j];

	for (int i = 0; i < M; i++)
	{
		int x1, x2, y1, y2;
		int total = 0;

		cin >> x1 >> y1 >> x2 >> y2;

		for (int j = x1; j <= x2; j++)
			total += sum[j][y2] - sum[j][y1 - 1];

		cout << total << '\n';
	}

	return 0;
}

전형적인 2차원 DP문제이며 자주 보였던 유형이다.

오랜만에 풀어서 시간이 좀 걸리긴 했지만 점화식을 세워 3차원 반복문으로 풀었다.

문제링크 : 2225번: 합분해 (acmicpc.net)

#include <iostream>
#include <vector>

using namespace std;

#define DIV 1000000000

int main() {

	int N, K;
	cin >> N >> K;

	vector<vector<int>> DP(K + 1, vector<int>(N + 1, 0));
	DP[0][0] = 1;

	for(int i = 1; i <= K; i++)
		for (int j = 0; j <= N; j++) {
			for (int k = 0; k <= j; k++)
			{
				DP[i][j] += DP[i - 1][j - k];
				DP[i][j] %= DIV;
			}
		}

	cout << DP[K][N] << endl;

	return 0;
}

크게 어렵지는 않았으나 root N 까지 돌려야 하는걸 한번에 알지못해 시간이 좀 걸렸다.

그외에는 쉬운 문제였다.

#define MAX 1000000000

#include <iostream>
#include <algorithm>

using namespace std;

bool IS_SAME_NUM(int n, int b) {

	int temp = n % b;
	n /= b;

	for (; n != 0; n /= b)
		if (temp != n % b)
			return false;

	return true;
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		int Answer = MAX;
		
		int N; cin >> N;

		if (N <= 2)
			Answer = N + 1;

		else
		{
			for (int i = 2; i * i <= N; i++)
			{
				if (IS_SAME_NUM(N, i))
				{
					Answer = min(i, Answer);
				}

				if (N % i != 0)
					continue;

				int temp = N / i - 1;

				if (temp > i)
					Answer = min(temp, Answer);
			}

			if (Answer == MAX)
				Answer = N - 1;
		}
		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}

SCPC 1회 첫번째 예선 2번문제였다.

어려운것 없었으며 그대로 시뮬레이션 돌리면 되는 문제였다.

다만 방향설정이 복잡하여 case를 잘 나눠야한다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef struct pos {
	int x;
	int y;
	int dir;
}pos;

pos temp;

void next_pos(int cur)
{
	if (cur == 0)
		temp.x++;
	else if (cur == 1)
		temp.y--;
	else if (cur == 2)
		temp.x--;
	else
		temp.y++;
}

void next(pos cur, char mirror)
{
	temp = cur;

	if (mirror == '1')
	{
		if (cur.dir == 0)
			temp.dir = 1;
		else if (cur.dir == 1)
			temp.dir = 0;
		else if (cur.dir == 2)
			temp.dir = 3;
		else
			temp.dir = 2;
	}

	else if(mirror == '2')
	{
		if (cur.dir == 0)
			temp.dir = 3;
		else if (cur.dir == 1)
			temp.dir = 2;
		else if (cur.dir == 2)
			temp.dir = 1;
		else
			temp.dir = 0;
	}

	next_pos(temp.dir);
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T, test_case;

	cin >> T;

	for (test_case = 0; test_case < T; test_case++)
	{
		int Answer = 0;
		int N; cin >> N;
		vector<string> arr(N);
		vector<vector<bool>> visited(N, vector<bool>(N, false));
		for (int i = 0; i < N; i++)
			cin >> arr[i];

		pos cur = { 0, 0, 3 };
		while (1)
		{
			if(cur.x < 0 || cur.x >= N || cur.y < 0 || cur.y >= N)
				break;

			if (!visited[cur.x][cur.y] && arr[cur.x][cur.y] != '0')
			{
				visited[cur.x][cur.y] = true;
				Answer++;
			}

			next(cur, arr[cur.x][cur.y]);
			cur = temp;
		}

		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;
}

SCPC 1회 첫번째 예선 1번 문제이다.

알고리즘이 딱히 필요하진 않았으며 case만 잘 나누면 쉽게 풀린 문제였다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T, test_case;

	cin >> T;
	for (test_case = 0; test_case < T; test_case++)
	{
		int Answer = 0;
		int N; cin >> N;
		queue<int> A;
		int temp;

		for (int i = 0; i < N - 1; i++)
		{
			cin >> temp;
			A.push(temp);
		}
		int end; cin >> end;
		int K; cin >> K;

		int start = 0;
		int last = -1;
		int cnt = 0;

		while (1)
		{
			if (start + K >= A.front())
			{
				last = A.front();
				A.pop();
			}
			else
			{
				if (last == -1)
					break;

				start = last;
				cnt++;

				if (start + K < A.front())
					break;
			}
			
			if (A.empty())
			{
				if (start + K < end)
				{
					if (last + K >= end)
					{
						start = last;
						cnt++;
						break;
					}
				}
				else
					break;
			}
		}

		if (start + K >= end)
			Answer = cnt + 1;
		else
			Answer = -1;

		cout << "Case #" << test_case + 1 << endl;
		cout << Answer << endl;
	}

	return 0;//Your program should return 0 on normal termination.
}