언제나 처음처럼

[문제 링크]

분할정복과 이분탐색이 섞인 문제인거같다. 이분탐색 풀이법이 생각나지 않아 다른사람들의 풀이법을 참고하였다. 3일 후에 다시한번 풀어봐야 겠다.

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

vector<int> dayMoney;
int N, M, sum;

bool Solution(int money)
{
	int temp = money, withdraw = 1;
	for (int i = 0; i < N; i++)
	{
		if (dayMoney[i] > money)
			return false;
		if (temp - dayMoney[i] < 0)
		{
			temp = money;
			withdraw++;
		}
		temp -= dayMoney[i];
	}
	return M >= withdraw;
}
int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		dayMoney.push_back(n);
		sum += n;
	}

	// binary_search //
	int start = 1, end = sum; // sum은 M이 1인 모든 금액을 더한 값
	int result;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (Solution(mid))	// 인출횟수가 M보다 작거나 같음 -> 인출금을 줄여보자
		{
			result = mid;
			end = mid -1;
		}
		else
			start = mid + 1;
	}
	cout << result << endl;
	return 0;
}

알고리즘 200일 프로젝트 - 39day

[문제 링크]

https://onlytrying.tistory.com/46

쿼드트리 문제와 동일하다. 다른점은 보드 크기가 3^N X 3^N 인 것과 보드를 쪼갤 때 4조각이 아닌 9조각으로 쪼갠다는 것이다.

쿼드트리 문제와 마찬가지로 (startY, startX)좌표를 시작으로 3^N X 3^N 크기 만큼의 보드를 검사한다.

숫자가 모두 같다면 더이상 쪼개질 수 없으므로 보드의 숫자를 카운팅 해준다.

필자는 0으로 초기화한 크기가 3인 배열을 하나 만들고 Array[보드의 숫자 + 1]++ 으로 숫자를 카운팅하였다.

#include <iostream>
using namespace std;

int board[2188][2188];
int numberCnt[3]; // MINUS ONE = 0, ZERO = 1, ONE = 2

void Solution(int N, int startY, int startX)
{
	if (N == 1) // 없어도 무방한 기저사례지만 코드 직관성과 효율성을 위해 추가
	{
		++numberCnt[board[startY][startX] + 1];
		return;
	}

	bool check = true;
	for (int i = startY; i < startY + N; i++)
	{
		for (int j = startX; j < startX + N; j++)
		{
			if (board[startY][startX] != board[i][j])
			{
				check = false;
				break;
			}
		}
		if (!check) break;
	}
	if (check)
	{
		++numberCnt[board[startY][startX] + 1];
		return;
	}

	int nextN = N / 3;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			Solution(nextN, startY + (nextN*i), startX + (nextN*j));
}
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	Solution(N, 0, 0);

	for (int i = 0; i < 3; i++)
		cout << numberCnt[i] << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 38day

[문제 링크]

https://onlytrying.tistory.com/42

AOJ의 QUADTREE 문제와 유사한 형태의 문제라고 생각한다. 따라서 알고리즘도 비슷하게 구현하였다.

먼저 (startY, startX)좌표를 시작으로 N X N 크기만큼 보드값을 검사한다. 모든 값이 일치한다면 숫자 1 or 0 으로 압축할 수 있다. 값이 일치하지 않다면 N/2 크기의 보드 4개로 나누고 나눠진 보드에 대해 위와 같은 작업을 반복한다.

나눠진 보드들이 반환하는 문자열을 합치고 시작 위치에 '(', 끝 위치에 ')'을 붙여주면 원하는 결과를 출력할 수 있다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<string> board;

string Solution(int N, int startY, int startX)
{
	bool check = true;
	for (int i = startY; i < startY+N; i++)
	{
		for (int j = startX; j < startX+N; j++)
		{
			if (board[i][j] != board[startY][startX])
			{
				check = false;
				break;
			}
		}
		if (!check) break;
	}
	if (check) return string(1,board[startY][startX]);

	int nextN = N / 2;
	string board1 = Solution(nextN, startY, startX);
	string board2 = Solution(nextN, startY, startX + nextN);
	string board3 = Solution(nextN, startY + nextN, startX);
	string board4 = Solution(nextN, startY + nextN, startX + nextN);

	return '(' + board1 + board2 + board3 + board4 + ')';
}
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		board.push_back(str);
	}
	cout << Solution(N, 0, 0) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 38day

[문제 링크]

2^N X 2^N 크기의 보드가 주어졌을 때, 이를 4등분 하면 2^(N-1) X 2^(N-1) 보드 4개로 나뉘게 된다.

또한 입력받은 좌표는 반드시 4개의 보드 중 한개의 보드 내에 존재하게 된다. 입력받은 좌표를 포함하는 보드에 대해 계속 나누면서 나뉜 보드의 크기가 2^1 X 2^1 이 되었을 때, 선택된 2X2 크기의 보드에는 반드시 입력받은 좌표가 존재하게 된다.

좌표와 일치하는 블록이 전체 보드판에서 가지는 값(방문 순서)을 출력해주면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <cmath>
using namespace std;

int Solution(int N, int col, int row, int start, int findCol, int findRow)
{
	if (N == 1)
	{
		if (col == findCol && row == findRow) return start;
		else if (col == findCol && row + 1 == findRow) return start + 1;
		else if (col + 1 == findCol && row == findRow) return start + 2;
		else return start + 3;
	} 

	int halfCol = pow(2, N) / 2 + col;
	int halfRow = pow(2, N) / 2 + row;

	if (findCol < halfCol && findRow < halfRow)
		return Solution(N - 1, col, row, start, findCol, findRow);

	else if (findCol < halfCol && findRow >= halfRow)
		return Solution(N - 1, col, halfRow, start + pow((pow(2,N)/2),2), findCol, findRow);

	else if (findCol >= halfCol && findRow < halfRow)
		return Solution(N - 1, halfCol, row, start + pow((pow(2, N)/2), 2) * 2, findCol, findRow);

	else
		return Solution(N - 1, halfCol, halfRow, start + pow((pow(2, N)/2) , 2) * 3, findCol, findRow);
}

int main(void)
{
	int N, r, c;
	cin >> N >> r >> c;
	cout << Solution(N, 0, 0, 0, r, c) << endl;
}

알고리즘 200일 프로젝트 - 37day