굳건하게

안녕하세요.

여행벌입니다.

문제는 단순하지만, 0.25초라는 짧은 제한 시간 때문에 DP를 이용해야만 풀 수 있는 문제입니다.

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

[알고리즘설계]

fibonachi(N)을 구하는데, fibonachi(1), fibonachi(0)이 몇 번 호출되는지 구하기 위해서는

fibonachi(N-1), fibonachi(N-2)를 구하는데 fibonachi(1), fibonachi(0) 이 몇 번 호출되는지 알고있으면 해결됩니다.

2차원 DP배열[2][N]을 다음과 같이 정의합니다.

DP[0][i] : fibonachi(i)를 구하는데 fibonachi(0) 의 호출 횟수.

DP[1][i] : fibonachi(i)를 구하는데 fibonachi(1) 의 호출 횟수.

그러면 아래와 같은 방정식이 성립합니다.

DP[0][i+1] = DP[0][i] + DP[0][i-1]

DP[1][i+1] = DP[1][i] + DP[1][i-1]

#include<iostream>

using namespace std;

int call_list[2][41]; // fibonachi(n)에 대해서 0이 호출되는 횟수를 0행, 1이 호출되는 횟수를 1행에 저장한다.


int main(void) {
	call_list[0][0] = 1;
	call_list[1][1] = 1;
	int total_case;
	cin >> total_case;
	while(total_case>0){
		int input;
		cin >> input;
		for (int i = 2; i <= 40; i++) {
			call_list[0][i] = call_list[0][i - 1] + call_list[0][i - 2];
			call_list[1][i] = call_list[1][i - 1] + call_list[1][i - 2];
		}
		cout << call_list[0][input] << " " << call_list[1][input];
		if(total_case != 1)
			cout << endl;
		total_case--;
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

오늘은 BFS 문제인 BOJ 1697 문제를 다뤄보겠습니다.

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

[알고리즘설계]

가능한 모든 경우를 BFS 탐색을 하며, 각 경우에 대해서 현재까지 몇 번 움직였는지 Count를 세줍니다.

가장 먼저 도착지점(End)에 도달하면, Count를 출력하며 종료합니다.

-주의사항

1.모든 경우에 대해서 움직이기 전에 가능한 index인지 체크해줘야 됩니다.

2.이미 와본 지점에 대해서는 더 진행할 필요가 없습니다.(이미 그전에 진행했으니까 Count가 클 수밖에 없음.)

#include<iostream>
#include<queue>

using namespace std;

void BFS(int, int);
bool check[100001];

int main(void) {
	int start, end;
	cin >> start >> end;
	BFS(start, end);
	return 0;
}

void BFS(int start, int end) {
	queue<int> q;
	queue<int> count;
	q.push(start);
	count.push(0);
	while (!q.empty()) {
		int x = q.front();
		int c = count.front();
		q.pop();
		count.pop();

		if (x == end) {
			cout << c;
			return;
		}
		if (x + 1 <= 100000 && !check[x+1]){
            check[x+1] = true;
			q.push(x + 1);
			count.push(c + 1);
		}
		if (2 * x <= 100000 && !check[2 * x]) {
            check[2*x] = true;
			q.push(2 * x);
			count.push(c + 1);
		}
		if (0 <= x-1 && !check[x-1]){
            check[x-1] = true;
			q.push(x - 1);
			count.push(c + 1);
		}
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

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

[알고리즘설계]

BFS 탐색을 하면서 탐색한 공간은 2로 바꿔주고, BFS탐색을 시행한 횟수를 출력합니다.

#include<iostream>
#include<queue>

using namespace std;

int map[50][50];
void BFS(int, int,int, int);

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

	int t;
	cin >> t;
	while (t--) {
		for (int i = 0; i < 50; i++)
			for (int j = 0; j < 50; j++)
				map[i][j] = 0;
		int row, column, k, x, y, count = 0;
		cin >> row >> column >> k;
		for (int i = 0; i < k; i++) {
			cin >> x >> y;
			map[x][y] = 1;
		}
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < column; j++) {
				if (map[i][j] == 1){
					BFS(i, j, row, column);
					count++;
				}
			}
		}
		cout << count << '\n';
	}
}

void BFS(int i, int j, int row, int column) {
	int x_dir[4] = { -1, 0, 1, 0 };
	int y_dir[4] = { 0, 1 , 0 , -1 };
	queue<int> x;
	queue<int> y;
	x.push(i);
	y.push(j);
	map[i][j] = 2;
	while (!x.empty()) {
		int x1 = x.front();
		int y1 = y.front();
		x.pop(), y.pop();
		for (int k = 0; k < 4; k++) {
			int next_x = x1 + x_dir[k];
			int next_y = y1 + y_dir[k];
			if (0 <= next_x && next_x < row && 0 <= next_y && next_y < column && map[next_x][next_y] == 1) {
				x.push(next_x);
				y.push(next_y);
				map[next_x][next_y] = 2;
			}
		}
	}
	return;
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.

안녕하세요.

여행벌입니다.

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

[알고리즘설계]

단순 구현 문제입니다.

#include<iostream>

int main(void) {
	int test_case;
	std::cin >> test_case;
	while (test_case) {
		int a, b, answer = 1;
		std::cin >> a >> b;
		for (int i = 0; i < b; i++)
			answer = answer * a % 10;
		if (answer == 0)
			std::cout << 10 << '\n';
		else
			std::cout << answer << '\n';
		test_case--;
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.