코딩하는 두꺼비

www.acmicpc.net/problem/16234

구현 문제이자 BFS로서 생각보다 크게 어렵진 않았지만 배열 크기 선언과 범위 설정하느라

계속 틀리다가 맞추었다. N*N으로 배열을 선언해야하는데 그 생각을 못하고 그냥 N으로 선언한 것이 패착이였다.

실제 시험장에서는 항상 변수 선언을 할때 생각을 하면서 해야할거 같다..

풀이는 BFS로 연합의 개수를 세고 각 2차원 배열로 각 연합의 인구수를 계산해서 저장을 해놓고

마지막에 인구수를 나눈 값을 넣어주는 형식으로 구성했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int N, L, R, ans, cnt = 1;
int map[51][51];
int visit[51][51];
int people[2555][2];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
queue<pair<int, int>> q;

void bfs(int x, int y) {
	q.push({ x, y });
	visit[x][y] = cnt;
	people[cnt][1]++;
	people[cnt][0] += map[x][y];

	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			int a = q.front().first;
			int b = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {		//국경을 열 수 있는지 확인
				int c = a + dx[j];
				int d = b + dy[j];
				if (c >= 0 && d >= 0 && c < N && d < N && visit[c][d] == 0 
					&& abs(map[a][b] - map[c][d]) >= L
					&& abs(map[a][b] - map[c][d]) <= R) {
					q.push({ c, d });
					visit[c][d] = cnt;
					people[cnt][0] += map[c][d];
					people[cnt][1]++;
				}
			}
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	while (1) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visit[i][j] == 0) {
					bfs(i, j);
					cnt++;	//연합 갯수 증가
				}
			}
		}
		for (int i = 0; i < N; i++) {	//연합 안의 사람들 재분배
			for (int j = 0; j < N; j++) {
				if (visit[i][j] > 0) {
					map[i][j] = people[visit[i][j]][0] / people[visit[i][j]][1];
				}
			}
		}
		if (cnt > N * N) {	//연합의 갯수가 N*N이면 중단
			break;
		}
		ans++;
		cnt = 1;
		memset(people, 0, sizeof(people));	//배열 초기화
		memset(visit, 0, sizeof(visit));
	}
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/14500

처음엔 경우의 수를 적게 생각하고 풀어서 계속 틀린 문제이다.

천천히 대칭을 포함한 경우의 수 19가지를 생각하고 그에 맞게 최대값을 구해주었다.

나 같은 경우에는 크게 5가지로 나누었다.

네모 모양 1가지 경우의 수를 계산하고

3개짜리 테트리스에 1개를 모든 방향에 붙인다는 생각으로 크게 2가지, 작게 7가지씩 14가지를 구성하였고

또한 2개짜리에 2개를 붙이는 경우를 2개씩 총 4가지를 계산해주었다.

#define _CRT_SECURE_NO_WARINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int map[501][501];
int N, M, ans, temp;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < N - 1; i++) {	// 네모모양 계산
		for (int j = 0; j < M - 1; j++) {
			ans = max(ans, map[i][j] + map[i + 1][j + 1] + map[i + 1][j] + map[i][j + 1]);
		}
	}
	for (int i = 0; i < N - 2; i++) {	//세로 3개짜리에 1개 붙이기
		for (int j = 0; j < M; j++) {
			temp = map[i][j] + map[i + 1][j] + map[i + 2][j];
			if (i + 3 < N) {
				ans = max(ans, temp + map[i + 3][j]);
			}
			if (j - 1 >= 0) {
				ans = max(ans, temp + map[i][j - 1]);
				ans = max(ans, temp + map[i + 1][j - 1]);
				ans = max(ans, temp + map[i + 2][j - 1]);
			}
			if (j + 1 < M) {
				ans = max(ans, temp + map[i][j + 1]);
				ans = max(ans, temp + map[i + 1][j + 1]);
				ans = max(ans, temp + map[i + 2][j + 1]);
			}
		}
	}
	for (int i = 0; i < N; i++) {	//가로 3개짜리에 1개 붙이기
		for (int j = 0; j < M - 2; j++) {
			temp = map[i][j] + map[i][j + 1] + map[i][j + 2];
			if (j + 3 < M) {
				ans = max(ans, temp + map[i][j + 3]);
			}
			if (i - 1 >= 0) {
				ans = max(ans, temp + map[i - 1][j]);
				ans = max(ans, temp + map[i - 1][j + 1]);
				ans = max(ans, temp + map[i - 1][j + 2]);
			}
			if (i + 1 < N) {
				ans = max(ans, temp + map[i + 1][j]);
				ans = max(ans, temp + map[i + 1][j + 1]);
				ans = max(ans, temp + map[i + 1][j + 2]);
			}
		}
	}
	for (int i = 0; i < N - 2; i++) {	//세로 2개짜리에 2개 붙이기
		for (int j = 0; j < M; j++) {
			temp = map[i][j] + map[i + 1][j];
			if (j - 1 >= 0) {
				ans = max(ans, temp + map[i+1][j - 1] + map[i + 2][j - 1]);
			}
			if (j + 1 < M) {
				ans = max(ans, temp + map[i+1][j + 1] + map[i + 2][j + 1]);
			}
		}
	}
	for (int i = 0; i < N; i++) {		//가로 2개짜리에 2개 붙이기
		for (int j = 0; j < M - 2; j++) {
			temp = map[i][j] + map[i][j + 1];
			if (i + 1 < N) {
				ans = max(ans, temp + map[i + 1][j + 1] + map[i + 1][j + 2]);
			}
			if (i - 1 >= 0) {
				ans = max(ans, temp + map[i - 1][j + 1] + map[i - 1][j + 2]);
			}
		}
	}
	cout << ans << "\n";
}

www.acmicpc.net/problem/3190

삼성 기출문제를 풀기 시작하여 첫문제로 정한 구현문제이다.

처음엔 조건을 보고 약간 겁먹었는데

천천히 조건을 보고 각 칸을 뱀의 몸, 사과, 빈 공간, 벽으로 나누었고

뱀은 덱을 사용해 구현하였다.

또한 다음 위치를 항상 저장하고 방향변수 및 시간 변수를 사용해서 풀었고

방향 전환을 할때 현재 방향을 고려하여 방향을 바꿔주었다.

#define _CRT_SECURE_NO_WARINGS
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

int N, K, L, cnt;		//기본 변수 3개, 시간변수
int dv, tv;		//방향변수, 방향전환 벡터 위치변수
int map[102][102];
deque<pair<int, int>> snake;
vector <pair<int, char>> v;

int main() {
	int a, b;
	char c;
	cin >> N;
	cin >> K;
	for (int i = 0; i < K; i++) {
		cin >> a >> b;
		map[a][b] = 1;
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		cin >> a >> c;
		v.push_back({ a,c });
	}
	a = 1, b = 2;
	snake.push_back({ 1, 1 });	//초기 뱀 세팅
	map[1][1] = 3;
	for (int i = 0; i <= N + 1; i++) {	//초기 벽 세팅
		map[0][i] = 2;
		map[i][0] = 2;
		map[i][N + 1] = 2;
		map[N + 1][i] = 2;
	}
	while (1) {
		snake.push_front({ a,b });	//뱀 머리 넣기
		cnt++;
		if (map[a][b] == 0) {		//공간이 빈 경우
			map[snake.front().first][snake.front().second] = 3;
			map[snake.back().first][snake.back().second] = 0;
			snake.pop_back();
		}
		else if (map[a][b] == 1) {		//사과가 있는 경우
			map[snake.front().first][snake.front().second] = 3;
		}
		else {		//뱀의 몸이나 벽일 경우
			break;
		}
		if (tv < v.size() && cnt == v[tv].first) {		//방향전환
			if (v[tv].second == 'L') {		//왼쪽
				if (dv == 0) {
					dv = 3;
				}
				else {
					dv -= 1;
				}
			}
			else {		//오른쪽
				if (dv == 3) {
					dv = 0;
				}
				else {
					dv += 1;
				}
			}
			tv++;
		}
		if (dv == 0) {		//다음 칸 이동
			b++;
		}
		else if (dv == 1) {
			a++;
		}
		else if (dv == 2) {
			b--;
		}
		else {
			a--;
		}
	}
	cout << cnt << "\n";
	return 0;
}