굳건하게

문제 : https://www.acmicpc.net/problem/13460

[ 알고리즘풀이 ]

1. 백트레킹을 이용해 10번 이동하는 모든 경우의 수를 구하기.

2. 각 경우의 수마다 구슬판을 기울여가며 빨간 구슬은 구멍에 빠지고, 파란 구슬은 구멍에 빠지지 않는 경우가 생긴다면 답을 갱신한다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, M, ans = 987654321;
char map[10][11] = {}, tempMap[10][11] = {};

void mapCopy(char tempMap[10][11]) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			tempMap[i][j] = map[i][j];
	return;
}

void goLeft(int* x, int* y) {
	char temp = tempMap[*x][*y];
	tempMap[*x][*y] = '.';
	int j = *y;
	while (j--) {
		if (tempMap[*x][j] != '.')
			break;
	}
	if (tempMap[*x][j] == 'O'){
		*y = j;
	}
	else{
		*y = j + 1;
		tempMap[*x][*y] = temp;
	}
	return;
}

void goRight(int* x, int* y) {
	char temp = tempMap[*x][*y];
	tempMap[*x][*y] = '.';
	int j = *y;
	while (j++) {
		if (tempMap[*x][j] != '.')
			break;
	}
	if (tempMap[*x][j] == 'O') {
		*y = j;
	}
	else {
		*y = j - 1;
		tempMap[*x][*y] = temp;
	}
	return;
}

void goUp(int* x, int* y) {
	char temp = tempMap[*x][*y];
	tempMap[*x][*y] = '.';
	int i = *x;
	while (i--) {
		if (tempMap[i][*y] != '.')
			break;
	}
	if (tempMap[i][*y] == 'O') {
		*x = i;
	}
	else {
		*x = i + 1;
		tempMap[*x][*y] = temp;
	}
	return;
}

void goDown(int* x, int* y) {
	char temp = tempMap[*x][*y];
	tempMap[*x][*y] = '.';
	int i = *x;
	while (i++) {
		if (tempMap[i][*y] != '.')
			break;
	}
	if (tempMap[i][*y] == 'O') {
		*x = i;
	}
	else {
		*x = i - 1;
		tempMap[*x][*y] = temp;
	}
	return;
}
void playGame(vector<int> v) {
	mapCopy(tempMap);
	// 빨간구슬, 파란구슬 위치를 따자.
	int redX, redY, blueX, blueY;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (tempMap[i][j] == 'R')
				redX = i, redY = j;
			if (tempMap[i][j] == 'B')
				blueX = i, blueY = j;
		}
	}
	// 기울이기 10번을 진행.
	for (int i = 0; i < 10; i++) {
		if (i >= ans)
			break;
		if (v[i] == 1) { // 왼쪽으로 기울이자.
			if (redX == blueX && redY > blueY) { // 파랑부터기울이자.
				goLeft(&blueX, &blueY);
				goLeft(&redX, &redY);
			}
			else {
				goLeft(&redX, &redY);
				goLeft(&blueX, &blueY);
			}
		}
		else if (v[i] == 2) { // 오른쪽으로 기울이자.
			if (redX == blueX && redY < blueY) {
				goRight(&blueX, &blueY);
				goRight(&redX, &redY);
			}
			else {
				goRight(&redX, &redY);
				goRight(&blueX, &blueY);
			}
		}
		else if (v[i] == 3) { // 위로 기울이자.
			if (redY == blueY && redX < blueX) {
				goUp(&redX, &redY);
				goUp(&blueX, &blueY);
			}
			else {
				goUp(&blueX, &blueY);
				goUp(&redX, &redY);
			}
		}
		else { // 아래로 기울이자.
			if (redY == blueY && redX < blueX) {
				goDown(&blueX, &blueY);
				goDown(&redX, &redY);
			}
			else {
				goDown(&redX, &redY);
				goDown(&blueX, &blueY);
			}
		}
		// 게임이 끝났는지 안끝났는지 체크.	
		if (map[blueX][blueY] == 'O')
			break;
		if (map[redX][redY] == 'O' && map[blueX][blueY] != 'O') {
			ans = min(ans, i + 1);
			break;
		}
		
	}
	return;
}

void Backtracking(vector<int> v) {
	if (v.size() == 10) {
		playGame(v);
		return;
	}
	for (int i = 1; i <= 4; i++) {
		v.push_back(i);
		Backtracking(v);
		v.pop_back();
	}
}

void Init(void) {
	vector<int> v;
	Backtracking(v);
	return;
}

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

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	Init();
	if (ans == 987654321)
		ans = -1;
	cout << ans;
	return 0;
}

알고리즘을 먼저 머리와 손으로 정리하고 구현해야하는데,,,,,,

남들보다 실행 시간도 오래걸리고 비효율적인 알고리즘 같다,,,,!!

반성 

문제 : https://www.acmicpc.net/problem/17837

[ 알고리즘풀이 ]

- 정의

chess[X][Y] : (X, Y) 지점에서의 체스판 상태

horseState[X][Y] : (X, Y) 지점에서의 체스판 위의 말들 상태

horse[X] : X 번 째 말의 현재 위치와 방향

1. 각 count 마다 0 ~ K - 1번까지 말들을 순회하며 말들을 move함수를 통해 이동시켜준다.

2. move 함수

- 현재 위치와 다음 위치를 계산한다.

- horseState를 순회하며 현재 위치에서 내가 아래에서부터 몇 번째 말인지 저장한다. ( 내 위의 말들은 같이 이동해야 하므로 )

- 다음 위치가 범위를 벗어났거나, 파란색 칸이면 방향을 바꿔준다.

changeDir[5] = { 0, 1, -1, 1, -1 }

curDir = curDir + changeDir[curDir];

( changeDir 배열을 다음과 같이 선언하면, 현재 방향에서 다음 방향을 쉽게 구할 수 있다. )

- 2번에 의해 방향이 바뀐 경우가 있으므로, 다시 다음 위치를 계산한다.

- 다음 위치가 범위를 벗어났거나, 파란색 칸이면 stop.

- 다음 위치가 흰색 칸이면 내 위의 말들을 다 같이 다음 위치로 이동하고, 그만큼 현재 위치에 pop을 진행.

- 다음 위치가 빨간색 칸이면 내 위의 말들을 다 같이 다음 위치로 거꾸로 이동하고, 그만큼 현재 위치에 pop을 진행.

3. move 함수를 진행할 때마다 게임이 끝났는지 check한다.

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

using namespace std;

int N, K, chess[12][12] = {}, changeDir[5] = { 0, 1, -1, 1, -1 }, dx[5] = { 0, 0, 0, -1, 1 }, dy[5] = { 0, 1, -1, 0, 0 }, a, b, c;
string horseState[12][12]; // 현재 chess판 위의 말 상태저장.
vector<pair<pair<int, int>, int>> horse; // 0 ~ K - 1번 위치저장.


bool checkMap(void) {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (horseState[i][j].length() >= 4)
				return true;
	return false;
}

void move(int i) {
	int curX = horse[i].first.first, curY = horse[i].first.second;
	int nextX = curX + dx[horse[i].second], nextY = curY + dy[horse[i].second];
	// j번 째 지점에 존재.
	int j = 0;
	for (j = 0; j < horseState[curX][curY].length(); j++){
		if (horseState[curX][curY][j] == char(i + '0')) {
			break;
		}
	}

	if ((nextX < 0 || N - 1 < nextX || nextY < 0 || N - 1 < nextY) || chess[nextX][nextY] == 2)
		horse[i].second = horse[i].second + changeDir[horse[i].second];

	nextX = curX + dx[horse[i].second], nextY = curY + dy[horse[i].second];

	if ((nextX < 0 || N - 1 < nextX || nextY < 0 || N - 1 < nextY) || chess[nextX][nextY] == 2)
		return;
	else { //흰색 빨간색
		if (chess[nextX][nextY] == 0){
			for (int k = j; k < horseState[curX][curY].length(); k++){
				horseState[nextX][nextY] += horseState[curX][curY][k];
				horse[horseState[curX][curY][k] - '0'].first.first = nextX;
				horse[horseState[curX][curY][k] - '0'].first.second = nextY;
			}
		}
		else {
			for (int k = horseState[curX][curY].length() - 1; k >= j; k--) {
				horseState[nextX][nextY] += horseState[curX][curY][k];
				horse[horseState[curX][curY][k] - '0'].first.first = nextX;
				horse[horseState[curX][curY][k] - '0'].first.second = nextY;
			}
		}
		j = horseState[curX][curY].length() - j;
		for (int k = 0; k < j; k++)
			horseState[curX][curY].pop_back();
	}

	return;
}

void playGame(void) {
	int count = 0;
	if (checkMap()) {
		cout << count;
		return;
	}
	while (count++ <= 1000) {
		for (int i = 0; i < K; i++) {
			move(i);
			if (checkMap()) {
				cout << count;
				return;
			}
		}
	}
	cout << -1;
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> chess[i][j];

	for (int i = 0; i < K; i++) {
		cin >> a >> b >> c;
		a--, b--;
		horseState[a][b] += char(i + '0');
		horse.push_back(make_pair(make_pair(a, b), c));
	}

	playGame();

	return 0;
}

문제를 이해할 때까지 제대로 읽자,,,,,

문제 : https://www.acmicpc.net/problem/16195

[ 알고리즘풀이 ]

dp[N][M] : N 을 M 개의 합으로 표현한 경우의 수.

dp[N][M] = dp[N - 1][M - 1] + dp[N - 2][M - 1] + dp[N - 3][M - 1];

#include<iostream>
#define M 1000000009
using namespace std;

int dp[1001][1001] = {}; // dp[N][M] : N을 M개로 표현

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	dp[1][1] = 1, dp[2][1] = 1, dp[2][2] = 1, dp[3][1] = 1, dp[3][2] = 2, dp[3][3] = 1;
	for (int i = 4; i <= 1000; i++) {
		for(int j = 2; j <= i; j++)
			dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 2][j - 1]) % M + dp[i - 3][j - 1]) % M;
	}

	int t, n, m;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		int sum = 0;
		for (int j = 1; j <= m; j++)
			sum = (sum + dp[n][j]) % M;
		cout << sum << '\n';
	}
	
	return 0;
}

문제 : https://www.acmicpc.net/problem/12865

[ 알고리즘풀이 ]

DP 문제입니다.

DP[K] : 무게를 K만큼 사용했을 때, 담을 수 있는 최대 가치. 라고 정의합니다.

1 ~ N 개의 물건을 차례대로 순회하며 DP 배열을 채우면 O(N * K) 만에 문제를 해결할 수 있습니다.

DP 배열 정의하는 것보다는 물건을 기준으로 배열을 채우는게 문제 풀이의 핵심인 것 같습니다. ( 같은 물건을 2번 사용하지 않을 수 있다. )

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int dp[100001] = {};

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

	int N, K, w, v;
	vector<pair<int, int>> list; // 무게와 가치
	list.push_back(make_pair(1, 1));

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> w >> v;
		list.push_back(make_pair(w, v));
	}

	for (int i = 1; i <= N; i++) {
		for (int j = K; j >= 1; j--) {
			if (list[i].first <= j) {
				dp[j] = max(dp[j], dp[j - list[i].first] + list[i].second);
			}
		}
	}
	
	cout << dp[K];
	
}