재시민

www.acmicpc.net/problem/1018

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

int main(void) {
	int Col; int Row;
	cin >> Col >> Row;

	vector<char> chess(51,0);
	vector<vector<char>> chessSpace(51,vector<char>(51,0));
	vector<char> chess1(51, 0);
	vector<vector<char>> chessSpace1(51, vector<char>(51, 0));

	vector<char> compare(51, 0);
	vector<vector<char>> chessCompare(51, vector<char>(51, 0));
	int i, j;
	for (i = 0;i < 8;i++) {
		for (j = 0;j < 8;j++) {
			if (i + j == 0 || (i + j) % 2 == 0) {// 0 이거나 2의 배수
				chessSpace[i][j] = 'W';
				chessSpace1[i][j] = 'B';
			}
			else {
				chessSpace[i][j] = 'B';
				chessSpace1[i][j] = 'W';
			}
		}
	}
	for (i = 0;i < Col;i++) {
		for (j = 0;j < Row;j++) {
			char A;
			cin >> A;
			chessCompare[i][j] = A;
		}
	}
	int count = 0;
	int count1 = 0;
	int ai, aj;
	
	vector<int> counter;
	for (ai = 0;ai <= Col - 8;ai++) {
		for (aj = 0;aj <= Row - 8;aj++) {
			int bi = 0; int bj = 0;
			for (i = ai;i < ai + 8;i++) {
				for (j = aj;j < aj + 8;j++) {
					if (chessSpace[bi][bj] != chessCompare[i][j]) {
						count++;
					}
					if (chessSpace1[bi][bj] != chessCompare[i][j]) count1++;
					if (bj <= 8)bj++;
				}if(bi<=8)bi++;
				 bj = 0;
			}counter.push_back(count);
			counter.push_back(count1);
			count = 0;
			count1 = 0;
			 bi = 0; 
		}
	}
	int min = *min_element(counter.begin(), counter.end());
	cout << min;
	return 0;
}

너무 코드가 더럽다

이게 최선인가 싶다.

1. 비교할 체스판 2개 생성

2. 기준점을 바꿔가면서 목표 체스판과 비교 후 count push

3. 최솟값 출력

www.acmicpc.net/problem/1708

수업시간에 배운 내용이라 복습겸 풀어보았다.

짐꾸리기로 풀다가 3시간은 날린 것 같다. 

다른 사람들 코드를 보니 거의 다 아니 모두가 Graham Scan 으로 푼 것 같다.

탈진 상태가 되고 배우는 마음으로 코드를 학습했다.

#include<iostream> 
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long int ll;
struct pos
{
	ll x, y;
};
vector<pos> vec;
bool compare_pos(pos p1, pos p2)
{
	if (p1.y != p2.y)
	{
		return p1.y < p2.y;
	}
	else
	{
		return p1.x < p2.x;
	}
}
long long int ccw(pos p1, pos p2, pos p3)//외적공식
{
	//음수 시계 
	//양수 반시계 
	//0 평행
	return (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x));
}

bool compare_rad(pos p1, pos p2)// 라디안 비교 가장큰거
{
	long long int cc = ccw(vec[0], p1, p2);
	if (cc)//라디안이 비교가능
		return cc > 0;
	else//라디안이 동일 , 수평일때
		return p1.x + p1.y < p2.x + p2.y; // 가장큰순서대로
}

int N;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);


	cin >> N;
	for (int i = 0; i < N; i++)
	{
		ll y, x;
		cin >> x >> y;
		vec.push_back({ x,y });
	}
	stack<pos> sta;
	sort(vec.begin(), vec.end(), compare_pos);
	sort(vec.begin() + 1, vec.end(), compare_rad);
	sta.push(vec[0]);//비교를 위한 최소 점 셋팅
	sta.push(vec[1]);
	pos first, second;
	for (int i = 2; i < N; i++)
	{
		while (sta.size() >= 2)
		{
			second = sta.top();
			sta.pop();
			first = sta.top();
			if (ccw(first, second, vec[i]) > 0)
			{
				sta.push(second);
				break;
			}
		}
		sta.push(vec[i]);
	}
	cout << sta.size();
}

다른 분의 코드를 거의 배꼈다. 정말 수치심이 든다.

하지만 이렇게 배워간다면 다른 문제를 풀 수 있는 발판이 된다면 오히려 괜찮을지도..?

원 코드는 ccw 의 함수 때문에 테스트 값에서 오류가 나 long long int 로 재정의 하였다. 

사실 문제 안에 변들의 180도를 넘지 않는 가장 큰 각도를 선정해서 볼록껍질을 만들라는 말이 있었다.

나는 이것을 싸그리 무시하고 짐꾸리기를 배웠으니 그렇게 해야지 라고 해서 못한 것 같다.

일찌감치 인정하고 다른 방법으로 풀었어야 했는데..

알고리즘 설명

1. 벡터안에 입력한 순서쌍들을 push_back 한다.

2. 기준점을 설정할 정렬을 한다.

3. 기준점을 잡고 나머지 점들과 ccw 의 결과를 이용한 정렬을 한다. 이때, ccw = 0 인 점이 존재한다면 x+y 값이 더큰 점에 true 를 부여한다. 

4. 스택에 기준점, 비교할 점 두개를 push 한다. 왜냐하면, ccw 를 하기 위한 최소조건이다.

5. 스택의 맨 뒤 원소 두개와 벡터의 모든 원소 ccw 한 값을 비교하면서 ccw 값이 양수인 점을 찾고 맞으면 push 아니면 break 한다.

6. 반복문이 종료되면 스택에는 꼭짓점이 될 점들만 남는다.