코딩무식자 전공생

문제출처: https://www.acmicpc.net/problem/2502

문제

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다. 

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다. 

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에  준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1≤A≤B 이다.  

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째  날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

입력

첫째 줄에는 할머니가 넘어온 날 D (3≤D≤30)와 그 날 호랑이에게 준 떡의 개수 K (10≤K≤100,000)가 하나의 빈칸을 사이에 두고 주어진다. 

출력

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤A≤B)가 존재한다. 

풀이

수학을 잘하는사람이 코딩도 잘 한다는 것을 느낀 문제입니다. 문제의 조건을 수식에맞게 변수로 식을세워서 풀면 금방 답이 구해지는 문제인데, 아직 그런 학습이 부족해서인지 다른분들의 코드를 보고서야 이해를 했습니다.  이런 부류의 문제를 많이 풀어봐야겠습니다.

풀이는 스폐셜 저지, 즉 답이 여러개 일 수 있다는 점, 그래서 첫날(a)과 둘째날(b)을 1로잡고 하나씩 탐색해도되는점, 문제가 피보나치의 패턴이라는것만 알면 쉽습니다......

규칙을 보죠. 피보나치패턴에의해  첫날에 a, 둘째날에b만큼 주니, 다음과같이 식을 만들 수 있습니다.

a->b->a+b->a+2b->2a+3b..... 

a가 1,b=1부터 가정하므로(답이 여러개일 수 있으니 쉽게 a,b가 1개라고 가정하면서 탐색해본다는 마인드) k에 대한식을 세워보면 k=fibo[d-2]*a+fibo[d-1]*b입니다. 이 식을 세울줄 아는 능력(수학적 재능...)만있으면 끝입니다. 여기서 중요한건 a를 구하고 b를 구한다는 것, fibo[d-2],fibo[d-1]은 각각 a에대한 비율,b에대한 비율이라는것입니다. a는 1부터탐색해보고, 이때 가정한 a에 대해 b에대한 식b=(k-a*fibo[n-1])%fibo[n-2])을 세워서 b에대한 식이 나누어 떨어지면 (갯수는 정수이므로)a와 b가 구해진 겁니다. 끝입니다.

코드

#include<iostream>
using namespace std;
int fibo[31];
int main()
{
	int d, k;
	cin >> d >> k;
	fibo[1] = fibo[2] = 1;
	for (int i = 3; i <= d; i++)
	{
		fibo[i] = fibo[i - 2] + fibo[i - 1];
	}
	//a와 b의 계수(비율)
	int a_profit = fibo[d - 2];
	int b_profit = fibo[d - 1];
	//k=fibo(d-2)a+fibo(d-1)b;
	int a, b;
	for (int i = 1;; i++)
	{
		//a는 1부터 탐색해본다.
		a = i;
		//b에대한 식에대해 나누어떨어지면 답 구한거임)
		if ((k - a_profit * a) % b_profit)
			continue;
		//이 때 b는 구해진 a에대해 구함.
		b = (k - a_profit * a) / b_profit;
		break;
	}
	cout << a << endl << b << endl;
}

결과

문제출처: https://www.acmicpc.net/problem/11312

문제

무엇이든 덮어버리는 것을 좋아하는 지은이는 한변의 길이가 A인 정삼각형을 한변의 길이가 B인 정삼각형으로 완전히 덮어 버리고자 한다. 

두개의 정수 A, B 가 주어지고, B ≤ A 이고, A를 B로 나눌수 있을때, 한 변의 길이가 A인 정삼각형을 완전하게 덮기 위한, 한변의 길이가 B인 정삼각형의 개수를 구하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (T ≤ 1000)

각각의 테스트 케이스는 한줄로 이루어져 있으며 두개의 정수 A, B 가 (1 ≤ B ≤ A ≤ 1,000,000, B|A) 주어진다.

출력

각 테스트 케이스마다 한변의 길이가 A인 정삼각형을 완벽하게 덮을 수 있는 한변의 길이가 B인 정삼각형의 최소 개수를 출력한다.

풀이

규칙찾기문제입니다. 노트에 알고리즘을 설계하고 그것을 소스코드로 구현하는 능력을 기르기 위해 일부러 노트에 카테고리명을 노트에풀기라고 지었습니다.

규칙을 찾아볼까요? (그려보면 암) 2 1 일 때 답=4, 3 1 일때 답=9,  4 1 일때 답=16 입니다. 따라서 b가1일때 정답은 a^2이죠. 그리고 문제조건에의해 a%b=0이어야하므로  4 2일때를보면 4, 그리고 6 2 일 때를보면 9, 6 3일때는 4입니다. 결국 정답은 (a/b)^2가됩니다. 주의할것은 int형범위를 넘길 수 있으므로 longlong형으로 정답을 출력해야합니다.

코드

#pragma warning(disable:4996)
#include<iostream>
using namespace std;
int main()
{
	int t;
	long long a, b;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		scanf("%lld%lld", &a, &b);
		printf("%lld\n", a / b * a / b);
	}
}

결과

문제출처: https://www.acmicpc.net/problem/2573

문제

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

풀이

구현이 까다로워서 3시간넘게고민한 문제입니다. 아직 구현력이 많이 부족한것같습니다.... 알고리즘은 다음과 같습니다.

1년이 지날 때마다 빙산의 상태를 나타내는 temp배열을 선언합니다. map배열에 변화를 주면 0이아닌 좌표가 상태가 갱신되면 인접한 모든 좌표들도 즉각적으로 변화하기때문에 각각의 정확한 좌표의변화를 나타낼 수 없습니다. 따라서 temp배열에 변화된좌표를복사해야합니다. 그리고 각 좌표의 상하좌우를 살피며 빙산의상태를 갱신하고, temp가 완성되면 또 1년뒤의 변화를 나타낼 수 있도록 다시 map에 상태를 넘겨줍니다. 그리고 전형적인 dfs를 해주면되는데, 연결요소의 갯수를 ice라는 변수로 세주고, dfs까지의 연산이 끝나면 1년뒤의 상태변화를위한 연산이 끝나므로 year++해주면서 ice가 2이상일때 year를 출력해주면됩니다. 최종적으로 "1년뒤 빙산의상태 저장->복사->dfs수행"이 1년치의 한번의 연산이됩니다. 주석으로 나름 상세히 작성해보았습니다.

코드

#include<iostream>
#include<cstring>
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int temp[300][300];
int visited[300][300];
int map[300][300];
int year;
int n, m;
int cnt;
void dfs(int y,int x);
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	while (1)
	{
		memset(visited, 0, sizeof(visited));
		memset(temp, 0, sizeof(temp));
		for (int i = 1; i < n - 1; i++)
		{
			//1년의 연산 끝나면 32행 다시 반복하기위해 
			//복사했던 배열을 다시 map에복사하고 temp초기화해야함
			for (int j = 1; j < m - 1; j++)
			{
				cnt = 0;
				//0이아닌 좌표일때 
				if (map[i][j]>0)
				{
					//상하좌우돌아다니며 0이아닌 현재좌표의 내년의 남아있는 높이를 temp에저장
					for (int k = 0; k < 4; k++)
					{
						int ny = dy[k] + i;
						int nx = dx[k] + j;
						if (nx >= 0 && nx < m && ny >= 0 && ny < n)
						{
							if (map[ny][nx] == 0)
								cnt++;
						}
					}
					//다돌아다님,그좌표에서 cnt뺸값을 temp에저장
					int num = map[i][j] - cnt;
					if (num <= 0)temp[i][j] = 0;
					else temp[i][j] = num;
					
				}
			
			}
		}
		//높이깎고 1년뒤의모습출력했을때잘 나오는지 확인testcase
		/*for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << temp[i][j] << " ";
			}
			cout << endl;
		}*/
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				map[i][j] = temp[i][j];
			}
		}
		int ice = 0;
		//1년지났으니 dfs를돌려서 연결요소갯수가 2개이상이면 year출력
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (!visited[i][j] && map[i][j] >0)
				{
					dfs(i, j);
					ice++;
				}
					
			}
		}
		//빙산높이 감소시키고 dfs완료했으니 1년지남.
		year++;
		if (ice > 1) {
			cout << year << endl;
			return 0;
		}
		else if (ice == 0)
		{
			cout << 0 << endl;
			return 0;
		}

		
	}
	
}
void dfs(int y, int x)
{
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++)
	{
		int ny = dy[i] + y;
		int nx = dx[i] + x;
		if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
			if (!visited[ny][nx] && map[ny][nx]>0)
			{
				dfs(ny, nx);
			}
		}
	}
}

결과

문제출처:https://www.acmicpc.net/problem/10026

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

풀이

색약일 때와 아닐때 각각 dfs를돌렸을 때의 연결요소 수를 출력하면됩니다. 색약일 때는 R->G 또는 G->R로 바꿔주면됩니다. 색약이 아닐 때 연산을 마치고 visited배열을 초기화해주고, dfs를 돌렸을 때 현재의 구간이 상하좌우의 구간과 문자가 같으면 계속해서 dfs를 돌려주면서 같은문자일때 체크해주면됩니다.

코드

#include<iostream>
#include<cstring>
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
using namespace std;
int n;
char map[101][101];
bool visited[101][101];
void dfs(int y,int x);
int main()
{
	cin >> n;
	//정상인의 연결갯수,색약인의 연결갯수
	int normal = 0, unnormal = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
		}
	}
	//정상인,색약인 총 두번 dfs필요
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (!visited[i][j])
			{
				dfs(i, j);
				normal++;
			}
		}
	}
	memset(visited, false, sizeof(visited));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == 'R')map[i][j] = 'G';
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (!visited[i][j])
			{
				dfs(i, j);
				unnormal++;
			}
		}
	}
	cout << normal << " " << unnormal << endl;
}
void dfs(int y, int x)
{
	visited[y][x] = true;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		//맵과 닿는 모든구간이 맵의요소와 같아야 dfs돌림
		if (ny >= 1 && ny <= 100 && nx >= 1 && nx <= 100) {
			if (!(visited[ny][nx]) && (map[y][x] == map[ny][nx]))
			{
				dfs(ny, nx);
			}
		}
	}
}

결과

문제출처: https://www.acmicpc.net/problem/2468

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오. 

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이

이 문제의 핵심은 "아무것도 안잠긴 영역이 있을 수 있다", "비의양은 0~높이-1까지 라는것입니다. 다른분들의 풀이를 봤는데 비의 양이 1부터~100까지로놓고 푼 분들도 많은데 풀이에 따라서 아무것도 안잠긴 영역은 무조건 존재할 수 없을  때도 있습니다. 비의양은 0(내리지않을 때)~ 높이까지라고 보는게 맞습니다. 이 때 비의 양이 높이까지라면 역시 안잠기는영역은 존재할 수 없습니다. 최대높이가 100까지이고 비의양에 100까지라서 비의양이 0~100까지일 때의 모든경우를 살펴야하는데  안잠길수있는영역이 있을수 있나요? 하지만 본 문제는 아무것도 안잠긴 영역이 있을 수 있다고 전제를깔아놓아서 2 1 1 1 1 일때는 0이 답이겠지만 이런 입력은 애초에 없다는 가정이 성립하므로 높이의 범위가 0~100, 0~99 둘다 되는것 같습니다. 

풀이는 간단합니다.  비의양이 1~100까지의 모든경우를 살피기위해 temp배열로 비의 양이 달라질때마다(커질 때 마다) 복사하여 dfs를 수행합니다. 그 때 마다 최대 안전구역을 갱신하여 최종적으로 가장크게 갱신된 값이 답이됩니다.  복사+높이가 달라질 때 마다 visited배열,temp배열 초기화 하는 것만 구현하고나면 나머지는 전형적인 dfs입니다.

코드

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int arr[101][101];
int temp[101][101];//모든경우를 복사해야됨
int visited[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
void dfs(int y, int x);
int n;
int main()
{
	//시작지점부터 시작지점의높이를뺀상태에서dfs돌림.
	//돌리고 다시 원상복구시키고
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> arr[i][j];
		}
	}
	int res = 0;
	//높이는 무조건1이상이고 비의 양은 0부터임!!!안내릴수도있음
	//따라서 무조건 testcase는 res가 1이상의값가지는 경우임
	
	for (int height = 0; height <= 100; height++)
	{
		memset(visited, 0, sizeof(visited));
		memset(temp, 0, sizeof(temp));
		int cnt = 0;//복사한 배열에서 안전영역갯수
		//각 높이일 때르 저장
		for (int i = 1; i <= n;i++)
		{
			for (int j = 1; j <= n; j++)
			{
				//안잠길 때 비의양뺴줌
				//안해도되는연산임
				if (arr[i][j] > height)
					temp[i][j] = arr[i][j] - height;
				//잠길때(음수,0)모두 0처리해야되므로
				//근데이미 0으로초기화시킨상태니 안해도됨
				/*else
					arr[i][j] = 0;*/
			}
		}
		//dfs
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (!visited[i][j] && temp[i][j])
				{
					dfs(i, j);
					cnt++;
				}
			}
		}
		res = max(res, cnt);
	}
	cout << res << endl;
}
void dfs(int y, int x)
{
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (1 <= ny && ny <= n && 1 <= nx && nx <= n)
		{
			if (!visited[ny][nx] && temp[ny][nx])
				dfs(ny, nx);
		}
	}
}

결과

문제출처: https://www.acmicpc.net/problem/2583

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

풀이

확실히 문제를 많이 풀수록 제가 고민하고 시행착오를 고치는 과정들이 는다는(?) 느낌이 듭니다. 처음에 제가 염려했던 건 2차원배열의 그래프를 모두 탐색하는데 O(n^2)이 걸리니 제한이 있지않을까 싶었지만 입력 변수의 범위가 0~100이므로 충분하다는것을 알았습니다. 그리고 약간 애를 먹은 부분이 처음에 x1,x2,y1,y2를 입력받고 이중for문에 x식 -> y식으로 적었다가 틀렷다는 것입니다. 습관이되있어서 그런건데, 실제로 그렇게 작성하면 4,0,6,2 일 때 (5,0),(5,1)는 범위가 어긋나서 체크되지않습니다. 따라서 y -> x식으로 작성해야됩니다.  그것만 유의하면됩니다.  주석으로 달아놨습니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int map[100][100];
int visited[100][100];
//사각형칠해진부분 1로 해놓고 0으로된 부분탐색,
//dfs돌릴때마다 지나간 라인0으로체크해줌.

void dfs(int x, int y);
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int m, n;
int res;
int main()
{
	int k, x1, y1, x2, y2;
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		//좌표조심! 4,0,6,2일때
		//y와 x의 식이 바뀌면 (5,0),(5,1)불가능! 
		for (int y = y1; y < y2; y++)
		{
			for (int x =x1; x < x2; x++)
			{
				visited[y][x] = 1;
			}
		}
	}
	vector<int>v;
	for (int i = 0; i<m; i++)
	{
		for (int j = 0; j <n; j++)
		{
			if (map[i][j]==0&&!visited[i][j])
			{
				res = 0;
				dfs(i, j);
				v.push_back(res);
			}
		}
	}
	cout << v.size() << endl;
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;
}
void dfs(int x, int y)
{
	visited[x][y] = 1;
	res++;
	for (int i = 0; i < 4; i++)
	{
		int ny = dy[i] + y;
		int nx = dx[i] + x;
		if (ny >= 0 && ny < n && nx >= 0 && nx < m)
		{
			if (map[nx][ny] == 0 && !visited[nx][ny])
				 dfs(nx, ny);
		}
	}
	
}

결과

문제출처: https://www.acmicpc.net/problem/11724

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

풀이

dfs,bfs는 개념을 이해하고 계속 문제를 풀어보는게 좋은 학습방법인 것 같습니다.  시작노드(1번노드)에서 dfs를 시작하면 연결된 노드들까지 모두 탐색이되고, 연결되지않은 노드들도 똑같이 dfs를돌려서 20행~27행 의 dfs를 몇번돌렸는지 세주면됩니다.

코드

#include<iostream>
using namespace std;
int visited[1001];
int graph[1001][1001];
void dfs(int x);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n, m;
	int u, v;
	int ans = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v;
		graph[u][v] = 1;
		graph[v][u] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!visited[i]) 
		{
			dfs(i);
			ans++;
		}
	}
	cout << ans << endl;
}
void dfs(int x)
{
	visited[x] = 1;
	for (int i = 1; i <= 1000; i++)
	{
		if (!visited[i] && graph[x][i])
			dfs(i);
	}
}

결과

문제출처: https://www.acmicpc.net/problem/1834

문제

N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다.

입력

첫째 줄에 2,000,000 이하의 자연수 N이 주어진다.

출력

첫 줄에 구하고자 하는 수를 출력한다.

풀이

간단해 보이는데 정답률이 낮은문제입니다.제 생각에 수학문제나 dp문제나 메모이제이션의 유무만 다르지 둘 다 규칙찾기문제같습니다.

답이될수 있는 자연수의 범위가 주어지지않았기 때문에 단순히 반복문for(int i=1; i<=200000;i++) 내부에서 1부터 i/n==i%3)인 수를 찾아서 더해가는 풀이는 답이될 수없습니다.  애초에 답이될수 있는 자연수의 범위는 1~200000도 아닙니다. 그럼 규칙을 찾아봅시다.

n=1일때 -> 없음

n=2일때 3

n=3일때 4, 8

n=4일때 5,10,15

n=5일때 6,12,18,24

보이시나요? 여기서 확실하게 알아야될 건 n=4,n=5일때 끝값이 15,24라는 겁니다. 규칙대로 각각 20,30은될 수 없습니다.

n=3일때 나머지로 나올 수잇는 수는 1,2,0으로 3가지인데, 0은 나눠서 나올 수가 없기 때문에 무조건 n-1가지밖에 없습니다.  마찬가지로 n=4일때 나머지는 0,1,2,3이 나올 수 있는데 0은 셈하지않으니 3번연산합니다. 마지막으로 입력값이 최대 20만이라 ans는 int형 범위를 초과할 수 있으므로 longlong 형으로 선언해주면됩니다. 이 것을 코드로 작성하면 끝입니다. 

코드

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	if (n == 0 || n == 1)
	{
		cout << 0 << endl; return 0;
	}
	long long ans = 0;
	for (int i = 2; i <= n; i++)
	{
		ans += (long long)(n + 1) * i;
	}
	cout << ans;
}

결과