코딩하는 두꺼비

www.acmicpc.net/problem/13458

쉬운 문제임에도 불구하고 시간초과와 변수 크기 때문에 꽤나 애먹었다..

또한 올림/내림 함수를 까먹어서 찾았고 또한 int형 숫자 두개를 나누면 절대 double형으로 결과값이 나오지 않는 다는 것도 알게 되었다.

오랜만에 푸는 문제였는데 브론즈임에도 불구하고 유의해야 할 점이 많이 있어서 기록하게 되었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

long long N, A, B, ans;
double C;
vector<double> lec;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A;
		lec.push_back(A);
	}
	cin >> B >> C;
	ans += N;
	for (int i = 0; i < N; i++) {
		lec[i] -= B;
		if (lec[i] > 0) {
			ans += ceil(lec[i] / C);
		}
	}
	cout << ans << "\n";
	return 0;
}

www.acmicpc.net/problem/1992

분할 정복의 대표격인 문제인 쿼드 트리이다.

예전에 프로그래머스 월간 챌린지에서 비슷한 문제가 나온적이 있었다. 그땐 개념을 제대로 몰라 막 풀었는데 이번에는 재귀를 사용해서 푸는 법을 알게 되어 이를 사용해 풀 수 있었다.

괄호를 넣어줘야되는 부분이 좀 까다로워서 고민을 많이 했는데 함수 호출전에 미리 넣어주는 방식으로 해결할 수 있었다.

이전에 Z라는 문제를 풀었는데 그때 답지를 보며 공부한 것이 크게 도움되었다.

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

int N;
int quad[65][65];
string ans;

void dfs(int x, int y, int z) {
	int check = 0;
	for (int i = x; i < x + z; i++) {
		for (int j = y; j < y + z; j++) {
			if (quad[x][y] != quad[i][j]) {
				check = 1;
				break;
			}
		}
	}
	if (check == 0) {
		ans += to_string(quad[x][y]);
	}
	else {
		z = z / 2;
		ans += "(";
		if (z == 1) {
			ans += to_string(quad[x][y]);
			ans += to_string(quad[x][y + 1]);
			ans += to_string(quad[x + 1][y]);
			ans += to_string(quad[x + 1][y + 1]);
		}
		else {
			dfs(x, y, z);
			dfs(x, y + z, z);
			dfs(x + z, y, z);
			dfs(x + z, y + z, z);
		}
		ans += ")";
	}
	return;
}

int main() {
	int c = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &quad[i][j]);
		}
	}
	dfs(0, 0, N);
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/2583

처음엔 모눈종이가 거꾸로 되있고 좌표로 직사각형을 입력받아야해서 조금 생각을 해야했다.

하지만 그 후엔 그냥 단순히 DFS를 구현하면 되는 쉬운 문제였다.

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

int m, n, k, cnt;
int map[101][101];
int visit[101][101];
vector<int> ans;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1,0,-1,0 };

void dfs(int a, int b) {
	cnt++;
	for (int i = 0; i < 4; i++) {
		if (a + dx[i] >= 0 && a + dx[i] < n 
			&& b + dy[i] >= 0 && b +dy[i] < m
			&& visit[a + dx[i]][b + dy[i]] == 0 && map[a + dx[i]][b + dy[i]] == 0) {
			visit[a + dx[i]][b + dy[i]] = 1;
			dfs(a + dx[i], b + dy[i]);
		}
	}
	return;
}

int main() {
	int a, b, c, d;
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++) {
		cin >> a >> b >> c >> d;
		for (int j = a; j < c; j++) {
			for (int k = b; k < d; k++) {
				map[j][k] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == 0 && map[i][j] == 0) {
				visit[i][j] = 1;
				cnt = 0;
				dfs(i, j);
				ans.push_back(cnt);
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
	return 0;
}