굳건하게

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2014 예선전 B번 문제인 Driving License 풀이를 해보겠습니다.

4차원 배열을 활용한 dp 문제로 어떻게 이런 아이디어를 내는지.. 정말 출제자나 푸신 분들이나 대단하네요...

저는 도저히 아이디어가 안 떠올라서 https://blog.encrypted.gg/86 님의 설명을 참고해서 문제를 풀었습니다.

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

[알고리즘풀이]

이 문제의 핵심 힌트는 오른쪽 또는 아래로만 이동할 수 있고, 최소 이동 횟수는 오직 방향 전환(turn)에 의존하는 점입니다.

DP[i][j][k][d]  : (0,0) 부터 (i,j) 까지 k번 turn하고 d( 0 : 왼->오, 1 : 위->아래) 방향으로 왔을 때 최소 연료양

row[i][j] : i 번째 row 에서 j ~ j + 1 column까지 이동하는데 필요한 연료.

column[i][j] : i ~ i + 1 row까지  j 번째 column에서 이동하는데 필요한 연료.

다음과 같이배열을 정의한다. 그러면, 다음과 같은 방정식이 성립한다.

DP[i][j][k][0] = min(dp[i][j - 1][k][0] + row[i][j - 1], dp[i][j - 1][k - 1][1] + row[i][j - 1])

DP[i][j][k][1] = min(dp[i - 1][j][k][1] + column[i - 1][j], dp[i - 1][j][k - 1][0] + column[i - 1][j])

따라서 DP배열을 다 채우고나면 목표지점인 (N,M)에 대해 K 를 작은 값부터 순회하며, 기준 연료양보다 낮은 값을 발견하면 거리를 출력하면 된다.

#주의#

DP배열을 미리 큰 값으로 초기화하지 않으면, 기준 연료양보다 낮은 값이 DP[N][M][0][0] 에서 발견되므로 항상 큰 값들로 초기화해줘야 된다.

#include<iostream>
#include<algorithm>

using namespace std;

int dp[101][101][200][2];
int row[100][100];
int column[100][100];

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

	int t;
	cin >> t;

	while (t--) {
		int r, c, l, g;
		cin >> r >> c >> l >> g;
		// row[i][j] 는 i 줄 j ~ j + 1까지의 연료.
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c - 1; j++)
				cin >> row[i][j];
		}
		// colum[i][j]는 i ~ i + 1 줄 j 의 연료.
		for (int i = 0; i < r - 1; i++)
			for (int j = 0; j < c; j++)
				cin >> column[i][j];

		int maxturn = 2 * max(r, c);
		// dp를 초기화시키자.
		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++)
				for (int k = 0; k <= maxturn; k++)
					for (int l = 0; l < 2; l++)
						dp[i][j][k][l] = 99999999;
		dp[0][0][0][0] = 0, dp[0][0][0][1] = 0;
		// dp를 먼저 채워보자.
		for (int j = 1; j < c; j++)
			dp[0][j][0][0] = dp[0][j - 1][0][0] + row[0][j - 1];
		for (int i = 1; i < r; i++)
			dp[i][0][0][1] = dp[i - 1][0][0][1] + column[i - 1][0];
		// 나머지는 점화식을 활용해 채워보자.
		for (int i = 1; i < r; i++)
			for (int j = 1; j < c; j++) {
				maxturn = 2 * max(i, j);
				for (int k = 1; k <= maxturn; k++) {
					dp[i][j][k][0] = min(dp[i][j - 1][k][0] + row[i][j - 1], dp[i][j - 1][k - 1][1] + row[i][j - 1]);
					dp[i][j][k][1] = min(dp[i - 1][j][k][1] + column[i - 1][j], dp[i - 1][j][k - 1][0] + column[i - 1][j]);
				}
			}
		// 답을 도출해보자.
		bool flag = false;
		maxturn = 2 * max(r, c);
		for (int k = 0; k <= maxturn; k++) {
			if (dp[r - 1][c - 1][k][0] <= g || dp[r - 1][c - 1][k][1] <= g) {
				cout << l * (r - 1 + c - 1) + k << '\n';
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << "-1\n";
		}

	}
}

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

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

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

감사합니다.

안녕하세요.

여행벌입니다.

방학이 끝나기 전에 예전에 풀었던 문제들도 포스팅을 해보려고 합니다.

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

[알고리즘설계]

출발점과 도착점이 원의 안과 밖으로 나뉜다면 카운트를 해준다.

#include<iostream>

using namespace std;

int main(void) {
	int total_case, planet_case; //테스트 케이스 횟수, 행성 갯수
	int x1, y1, x2, y2; //출발점좌표와 도착점좌표
	int count = 0; //행성이탈횟수를 세주는 변수
	int x3, y3, r; //행성의 중점과 반지름
    cin >> total_case;
	while (total_case > 0) { //전체 테스트 횟수
		count = 0; //테스트마다 count를 초기화 해준다.
        cin >> x1 >> y1 >> x2 >> y2 >> planet_case;
		for (int i = 0; i < planet_case; i++) {
        	cin >> x3 >> y3 >> r;
			if (((((x1 - x3)*(x1 - x3) + (y1 - y3)*(y1 - y3)) >= r * r)
				&& ((x2 - x3)*(x2 - x3) + (y2 - y3)*(y2 - y3) <= r * r))
				//출발점이 원 밖, 도착점이 원 안 인 경우
				||
				((((x1 - x3)*(x1 - x3) + (y1 - y3)*(y1 - y3)) <= r * r)
					&& ((x2 - x3)*(x2 - x3) + (y2 - y3)*(y2 - y3) >= r * r))) {
				count++;
			}
				//출발점이 원 안, 도착점이 원 밖 인 경우
		}
		total_case--;
        cout << count << '\n';
	}
}

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

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

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

감사합니다.

안녕하세요.

여행벌입니다.

문제는 단순하지만, 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);
		}
	}
}

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

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

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

감사합니다.