코딩무식자 전공생

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

문제

평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 중 하나이다. 그림-1은 1번, 2번, 3번 세 장의 색종이가 순서대로 놓인 상태를 보여준다.

그림-1

여기에 그림-2에서 보인 것처럼 4번 색종이가 하나 더 놓이면 3번 색종이는 완전히 가려서 보이지 않게 된다. 그리고, 1번 색종이와 2번 색종이는 부분적으로 가려 보이며, 4번 색종이는 완전히 보이게 된다.

그림-2

N장의 색종이가 주어진 위치에 차례로 놓일 경우, 각 색종이가 보이는 부분의 면적을 구하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 색종이의 장수를 나타내는 정수 N (1 ≤ N ≤ 100)이 주어진다. 이어서 N장의 색종이에 관한 입력이 각 색종이마다 한 줄씩 차례로 주어진다. 색종이가 놓이는 평면은 가로 최대 101칸, 세로 최대 101칸으로 구성된 격자 모양이다. 격자의 각 칸은 가로, 세로 길이가 1인 면적이 1인 정사각형이다. 

편의상 가로 6칸, 세로 6칸으로 이루어진 격자의 예를 들어 설명하면, 각 칸에 표시된 값 (a,b)는 해당 칸의 번호를 나타낸다. 가장 왼쪽 아래의 칸은 (0,0) 가장 오른 쪽 위의 칸은 (5,5)이다. 

색종이가 놓인 상태는 가장 왼쪽 아래 칸의 번호와 너비, 높이를 나타내는 네 정수로 표현한다. 예를 들어, 위 그림에서 회색으로 표시된 색종이는 (1,4)가 가장 왼쪽 아래에 있고 너비 3, 높이 2이므로 1 4 3 2로 표현한다. 색종이가 격자 경계 밖으로 나가는 경우는 없다. 

출력

입력에서 주어진 순서에 따라 N장의 색종이를 평면에 놓았을 때, 입력에서 주어진 순서대로 각 색종이가 보이는 부분의 면적을 한 줄에 하나씩 하나의 정수로 출력한다. 만약 색종이가 보이지 않는다면 정수 0을 출력한다. 

풀이

좌표상에서 색종이(사각형)가 겹칠 때 겹치는 부분의 넓이, 각 사각형의 보이는 넓이 등의 문제는 각 색종이(사각형)를 좌표상에 각각의 숫자로 칠하고 칠해진 부분의 합을 출력하면됩니다. 

이 문제도 살펴보면, 2가지색종이를 칠할 때 첫번째 색종이의 좌표들을 모두 1로 칠하고 그다음 색종이를 2, 다음 색종이를 3.... 이렇게 칠하면 최종적으로 좌표상에 칠해져있는 숫자의 합이 그 색종이의 부분넓이(문제에서 원하는 답)가 됩니다.

코드

#include<iostream>
#include<vector>
using namespace std;
int map[102][102];
int main()
{
	int n;
	int x, y, w, h;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x >> y >> w >> h;
		for (int a = x; a < x + w; a++)
		{
			for (int b = y; b < y + h; b++)
			{
				map[a][b] = i;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		int sum = 0;
		for (int a = 0; a < 101; a++)
		{
			for (int b = 0; b < 101; b++)
			{
				if (map[a][b] == i)
					sum++;
			}
		}
		cout << sum << endl;
	}
}

결과

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

문제

수많은 토너먼트를 거쳐 최종 플레이어 $$N명이 남아있다. 각 플레이어는

$$M장씩의 숫자가 적힌 카드를 가지고 있으며, 이들은 매 턴 자신이 가진 카드 중 가장 큰 카드를

두고 비교를 하는데, 그 카드들 중 가장 큰 수를 가진 플레이어가 1점을 획득한다. 그 턴에

사용된 카드는 버리기로 한다. ( 가장 큰 수를 가진 플레이어는 여러 명일 수 있다. )

$$M번의 경기 후 가장 많은 점수를 획득한 플레이어는 몇 번 플레이어인가 ?

입력

입력의 첫 줄에 플레이어의 수 N과 가진 카드 수 M이 입력 된다. (2≤N≤100,1≤M≤100)

그 다음 N줄에 걸쳐 각 플레이어가 들고 있는 카드에 적힌 숫자들이 입력된다. (1≤ 카드에 적힌 숫자 ≤100)

출력

최종 승자의 번호를 출력한다.

플레이어의 번호는 1번부터 $$N번까지 입력받은 순서로 주어진다고 가정한다.

가장 많은 점수를 획득한 플레이어가 여러 명일 경우, 빈칸을 사이에 두고 플레이어들의

번호를 오름차순으로 출력한다.

풀이

규칙찾기문제는 규칙만 찾으면  구현이 쉬운반면 이런 시뮬레이션 구현문제는 확실히 기본적인 구현능력이 있느냐 없느냐를 판단하기에 좋은 것 같습니다. 말그대로 생각한 것을 그대로 소스로 구현하는 능력이 필요합니다. (기업의 코딩테스트가 어려운 알고리즘 문제가 아닌 시뮬레이션,구현문제를 많이 내는 이유가 이런 것 때문 아닐까요??)

소스코드를 보면 알겠지만 말그대로 의식의 흐름대로 풀어나갔습니다. 어려운 내용은 없고 설명은 주석으로 대체하겠습니다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100][100];
int score[100];
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < m; j++) 
			cin >> arr[i][j];
		sort(arr[i], arr[i] + m);
	}
	//갖고있는 3장씩의 카드중
	for (int i = 0; i < m; i++)
	{
		//값을 비교할 초깃값을 0으로설정
		int temp = 0;
		//가장 큰값구하고
		for (int j = 0; j < n; j++)
			temp = max(temp, arr[j][m - i - 1]);
		//구해진 가장 큰값을 가진 사람점수++;
		for (int j = 0; j < n; j++)
			if (temp == arr[j][m - i - 1])
				score[j]++;
	}
	//가장큰 값을 구하고,
	int max_score = 0;
	for (int i = 0; i < n; i++)
		max_score = max(max_score, score[i]);
	//그 값을 가지는 사람을 출력
	for (int i = 0; i < n; i++)
		if (max_score == score[i])
			cout << i + 1 << " ";
	cout << endl;
}

결과