굳건하게

문제 : 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];
	
}

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

[ 알고리즘풀이 ]

 자료구조 우선순위큐를 이용하면 조금 더 간단하게 해결할 수 있는 문제입니다.

1. R연산

- 원소의 값이 1 ~ 100 사이이므로, count 배열을 선언해 행을 순회하며 값들을 count 한다. 이때, count된 값들은 0으로 초기화한다.

- count한 값들을 오름차순 기준 우선순위큐에 (count, 해당 index) 를 push 한다.

- 우선순위큐의 원소를 하나씩 뽑아가며 map에 갱신한다.

2. C연산

- 위의 과정을 열을 순회하며 진행하면 된다.

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int map[100][100] = {};
int r, c, k, t, row = 3, col = 3;

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

	cin >> r >> c >> k;
	r--, c--;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			cin >> map[i][j];

	int ans = 0;
	while (map[r][c] != k && ans <= 100) {
		if (row >= col) { //R연산
			int m = -1;
			for (int i = 0; i < row; i++) {
				priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
				int count[101] = {};
				// 행을 순회하며 count
				for (int j = 0; j < col; j++){
					count[map[i][j]]++;
					map[i][j] = 0;
				}
				// count를 기준으로 정렬
				for (int j = 1; j <= 100; j++)
					if (count[j])
						pq.push(make_pair(count[j], j));
				// 정렬된 새로운 값들을 대입하기.
				m = max(m, int(pq.size() * 2));
				int len = pq.size();
				for (int j = 0; j < len && j < 50; j++) {
					map[i][2 * j] = pq.top().second;
					map[i][2 * j + 1] = pq.top().first;
					pq.pop();
				}
			}
			// row, col 갱신
			col = m;
		}
		else { //C연산
			int m = -1;
			priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
			for (int j = 0; j < col; j++) {
				int count[101] = {};
				// 행을 순회하며 count
				for (int i = 0; i < row; i++){
					count[map[i][j]]++;
					map[i][j] = 0;
				}
				// count를 기준으로 정렬
				for (int i = 1; i <= 100; i++)
					if (count[i])
						pq.push(make_pair(count[i], i));
				// 정렬된 새로운 값들을 대입하기.
				m = max(m, int(pq.size() * 2));
				int len = pq.size();
				for (int i = 0; i < len && i < 50; i++) {
					map[2 * i][j] = pq.top().second;
					map[2 * i + 1][j] = pq.top().first;
					pq.pop();
				}
			}
			// row, col 갱신
			row = m;
		}
		ans++;
	}

	if (ans > 100)
		cout << -1;
	else
		cout << ans;
}

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

[ 알고리즘풀이 ]

1. 사냥꾼이 현재 열에서 행을 순회하며 상어가 있다면 잡습니다.

2. 상어를 전체적으로 이동해줍니다.

- 현재 상어의 위치와 이동한 상어의 위치를 따로 저장해줘야되므로 tempMap을 선언해 이동한 상어의 위치를 따로 저장해준 후, 이동이 끝나고 현재 map에 copy 해줍니다.

- 상어의 이동은 방향이 1, 2(위 아래)로 움직일 때는 (R - 1) * 2 씩 움직이는 것은 제자리로 돌아오므로 현재 상어의 velocity % ( (R - 1) * 2 ) 만큼만 실제로 이동해주면 되고, 방향이 3, 4( 오른쪽 왼쪽)으로 움직일 때는 (C - 1) * 2 씩 움직이는 것을 제자리로 돌아오므로 현재 상어의 velocity % ( ( C - 1) * 2 ) 만큼만 이동해주면 됩니다.

- 현재 위치( x, y ) 가 경계선에 닿아있고, 방향이 벽을 향하고 있다면 방향을 반대로 돌려줍니다.

- dx[5] = { 0, -1, 1, 0, 0, }, dy[5] = { 0, 0, 0, 1, -1 } 배열을 이용하면 현재 위치 ( x, y )에서 방향이 d일 때 다음 위치는 ( x + dx[d], y + dy[d] ) 로 쉽게 구할 수 있습니다.

#include<iostream>

using namespace std;

typedef struct shark {
	int velocity, dir, size;
};

shark map[101][101] = {};
int R, C, M, ans = 0, a, b, c, d, e, dx[5] = { 0, -1, 1, 0, 0 }, dy[5] = { 0, 0, 0, 1, -1 };

void moveShark(void) {
	shark tempMap[101][101] = {};
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (map[i][j].size != 0) { //상어가 있다면 이동.
				int x = i, y = j, s = map[i][j].velocity, d = map[i][j].dir;
				if (d <= 2)
					s = s % ((R - 1) * 2);
				else
					s = s % ((C - 1) * 2);
				for (int k = 0; k < s; k++) {
					if (x == 1 && d == 1)
						d = 2;
					if (x == R && d == 2)
						d = 1;
					if (y == 1 && d == 4)
						d = 3;
					if (y == C && d == 3)
						d = 4;
					x += dx[d];
					y += dy[d];
				}

				if (tempMap[x][y].size < map[i][j].size)
					tempMap[x][y] = { map[i][j].velocity, d, map[i][j].size };
			}
		}
	}

	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			map[i][j] = tempMap[i][j];

	return;
}

void getFish(int j) {
	for (int i = 1; i <= R; i++) {
		if (map[i][j].size != 0) {
			ans += map[i][j].size;
			map[i][j] = { 0, 0, 0 };
			break;
		}
	}
}

void playFishing(void) {
	// j는 현재 낚시꾼 위치.
	for (int j = 1; j <= C; j++) {
		// 낚시를 한다.
		getFish(j);
		// 상어들 이동.
		moveShark();
	}
	return;
}

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

	cin >> R >> C >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c >> d >> e;
		map[a][b] = { c,d,e };
	}
	playFishing();
	cout << ans;
}

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

[ 알고리즘풀이 ]

 1. 드래곤 커브는 X 세대에서는 전 세대까지 왔던 길을 반대로 90도 시계 방향으로 회전 시켜서 진행한다.

예를 들어, 문제 예시 드래곤 커브를 보자.

0세대에서는 x축이 커지는 방향( 0 방향 )으로 이동을 한다.

1세대에서는 그 전 세대까지 왔던 길( 0 방향으로 이동 ) 을 시계 방향으로 회전해서 y 좌표가 감소하는 방향( 1 방향 )으로 이동한다.

2세대에서는 그 전 세대까지 왔던 길( 0 방향 -> 1 방향 ) 을 반대로 1방향 -> 0 방향 순으로 시계 방향으로 회전해서 ( 2방향 -> 1방향 ) 으로 이동한다.

3세대에서는 그 전 세대까지 왔던 길( 0방향 -> 1방향 -> 2방향 -> 1방향 ) 을 반대로 시계 방향으로 회전해서 ( 2방향 -> 3방향 -> 2방향 -> 1방향 ) 으로 이동한다.

 즉, 기존까지 이동해온 길들을 저장하고 있다가, 새로운 세대에서는 그 길들을 역순으로 순회하며 방향을 1씩 증가시켜 이동해야한다. 이때, 이동한 부분은 1로 체크한다.

 2. 이동이 끝나면, 4개의 점이 1인 갯수를 count 한다.

#include<iostream>
#include<vector>
#include<deque>
#include<algorithm>
int map[101][101] = {}, N, x, y, d, g;

using namespace std;

int countSquare(void) {
	int ans = 0;
	for (int i = 0; i < 100; i++)
		for (int j = 0; j < 100; j++)
			if (map[i][j] && map[i + 1][j] && map[i][j + 1] && map[i + 1][j + 1])
				ans++;
	return ans;
}

void DragonCurve(int x, int y, int d, int g) {
	vector<int> dir;
	dir.push_back(d);

	int sx = x, sy = y;
	map[sy][sx] = 1;
    //첫 번째 세대 이동.
	if (d == 0)
		sx++;
	else if (d == 1)
		sy--;
	else if (d == 2)
		sx--;
	else
		sy++;
	map[sy][sx] = 1;

	for (int i = 1; i <= g; i++) {
		vector<int> temp;
        // 이전세대에서 이동한 길을 역순 + 시계방향회전해서 저장
		for (int j = 0; j < dir.size(); j++)
			temp.push_back((dir[dir.size() - 1 - j] + 1) % 4);
        // 이동.
		for (int j = 0; j < temp.size(); j++) {
			if (temp[j] == 0)
				sx++;
			else if (temp[j] == 1)
				sy--;
			else if (temp[j] == 2)
				sx--;
			else
				sy++;
			map[sy][sx] = 1;
		}
        // 새롭게 이동한 길을 저장.
        for (int j = 0; j < temp.size(); j++)
			dir.push_back(temp[j]);
	}
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x >> y >> d >> g;
		DragonCurve(x, y, d, g);
	}
	cout << countSquare();

}

드래곤 커브 예시를 잘 보면 2차원 배열 Map[row][column] 에서

row가 y 값, colum이 x 값인 것을 확인할수 있다.

이 부분을 캐치하지못하고 x 값을 row, y 값을 column으로 생각해서 구현하면

저처럼 '틀렸습니다.' 를 받을 수 있습니다,,,