[BAEKJOON] 1330, 1926, 15428

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[bronze 5, 1330 두 수 비교하기] - 구현

3항 연산자를 중첩하여 해결해보자

#include <iostream>
using namespace std;

int main() {
	int A, B;
	scanf("%d %d", &A, &B);
	A == B ? printf("==") : A > B ? printf(">") : printf("<");
}

[sliver 1, 1926 그림] - 너비우선탐색(BFS)

전형적인 너비우선탐색

#include <iostream>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

int n, m;
int map[501][501];
bool visit[501][501];

int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

bool range(int y, int x) {
	return y < 0 || x<0 || y>n || x>m || visit[y][x];
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &map[i][j]);

	int picture_ea = 0, picture_size = 0;
	queue<pair<int, int> > q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1 && !visit[i][j]) {
				int size = 1;
				visit[i][j] = true;
				picture_ea++;
				q.push({ i, j });
				while (!q.empty()) {
					pair<int, int> out = q.front(); q.pop();
					for (int d = 0; d < 4; d++) {
						int ny = out.first + dy[d];
						int nx = out.second + dx[d];
						if (!range(ny, nx) && map[ny][nx]) {
							size++;
							visit[ny][nx] = true;
							q.push({ ny, nx });
						}
					}
				}
				picture_size = picture_size > size ? picture_size : size;
			}
		}
	}
	printf("%d\n%d", picture_ea, picture_size);
}

 

[gold 5, 20002 사과나무] - 누적 합(Prefix Sum)

누적 합 (Prefix Sum)에 대한 점화식을 습득하는 것이 중요하다.

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

int N;
int map[301][301];
int prefixSum[301][301];

int main() {
	scanf("%d", &N);

	int answer = -(1001 * 1001);
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++) {
			prefixSum[i][j] = map[i][j] 
				+ prefixSum[i - 1][j] 
				+ prefixSum[i][j - 1] 
				- prefixSum[i - 1][j - 1];
		}

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++) {
			int len = min(N - i, N - j);
			for (int k = 0; k <= len; k++) {
				int calc = prefixSum[i + k][j + k] 
					- prefixSum[i - 1][j + k] 
					- prefixSum[i + k][j - 1] 
					+ prefixSum[i - 1][j - 1];
				answer = max(answer, calc);
			}
		}

	printf("%d", answer);
}