#include<stdio.h>
typedef unsigned char uc;
typedef unsigned short us;
static const int MAX_SIZE = 2501;

int main()
{
	int i, j, k;
	us N, M;
	scanf("%hu %hu", &N, &M);
	short size = N * M;

	int result = 0;
	uc a[MAX_SIZE];
	uc b[MAX_SIZE];


	for (i = 0; i < size; ++i)
	{
		scanf("%1d", &a[i]);
		/*scanf(" %c", &a[i]);
		a[i] -= 48;*/
	}
	for (i = 0; i < size; ++i)
	{
		scanf("%1d", &b[i]);
		/*scanf(" %c", &b[i]);
		b[i] -= 48;*/
	}
	

	if (N < 3 || M < 3)
	{
		for (i = 0; i < size; ++i)
		{
			if (a[i] != b[i])
			{
				printf("-1");
				return 0;
			}
		}
		printf("0");
		return 0;
	}


	for (i = 0; i <= N - 3; ++i)	
	{
		for (j = M * i; j <= M * (i + 1) - 3; ++j)
		{
			if (a[j] != b[j])
			{
				a[j + (M * 0)] = !a[j + (M * 0)]; a[j + (M * 0) + 1] = !a[j + (M * 0) + 1]; a[j + (M * 0) + 2] = !a[j + (M * 0) + 2];
				a[j + (M * 1)] = !a[j + (M * 1)]; a[j + (M * 1) + 1] = !a[j + (M * 1) + 1]; a[j + (M * 1) + 2] = !a[j + (M * 1) + 2];
				a[j + (M * 2)] = !a[j + (M * 2)]; a[j + (M * 2) + 1] = !a[j + (M * 2) + 1]; a[j + (M * 2) + 2] = !a[j + (M * 2) + 2];
				++result;
			}
		}

		if (a[M - 2] != b[M - 2] || a[M - 1] != b[M - 1])
		{
			result = -1;
			break;
		}
	}

	for (i = size - 1; size - (M * 2) < i; --i)
	{
		if (a[i] != b[i])
		{
			result = -1;
			break;
		}
	}

	printf("%d", result);
	return 0;
}

약 30분동안 고민했지만 로직이 생각나지 않았던 문제.. 나에게는 너무 어려웠다..

||사용 기법

• 그리디

||풀면서 느낀 것

• 여러 Input값을 생각 못하고 테스트 케이스만 통과되면 제출하는 버릇이 있다.

그래서 그런지 여러 예외 처리를 하지 못하는 모습을 보이고 있다.

반례 또한 스스로 생각해야 하는데 질문 게시판에서 찾아보게되더라 =~=

이런 다양한 Input값을 통한 예외, 반례 이런걸 스스로 생각 하는 습관을 들일것이다.

• 올바른 자료형 채택

이번에는 자료형을 무작정 int가 아닌 제한된 범위에 맞는 자료형을 맞추려 시도했다.

근데 꼼꼼히 생각하지 않았는지 이 때문에 여러 문제가 생기고 시간이 많이 소요됐다.

특히 배열의 최대 사이즈가 2500인데 unsigned char로 잡는 바람에 로직이 다 맞음에도 틀렸다. 시발

• 좀 더 꼼꼼한 설계

위와 비슷한 맥락이다. 항상 문제를 파악하고 설계를 하고 손코딩을 해보지만 설렁설렁한다는 느낌이 있어서

이번에 시간이 많이 소요되었다. 이번에 반복문에서 out of range, out of bound 도 많이 났었고

인덱스 규칙도 하나를 빼먹거나 해서 좀 꼼꼼하게 설계를 해야겠다.

||새로 알게 된것

• byte라는 타입은 C++ 17에 추가 되었으며(std::byte) 산술 연산이 불가능하다.

이번에 알맞은 자료형을 사용하려고 하면서 byte를 사용해봤는데 산술연산이 불가능했다.

나중에 연산이 안되는 점을 이용할 수 도 있겠다.

연산을 하려면 char종류나 uint8을 사용하면 되겠다.

||나아 진것

• 문제 파악

예전에는 난독증 마냥 읽어도 무슨말인지 모르는 경우가 많았는데 

최근에는 문제 해석은 잘 되는듯 하다!

이 문제 덕분에 우선순위 큐를 처음으로 사용하게 되었다.

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

int main()
{
	int N;
	cin >> N;

	priority_queue<int, vector<int>,greater<int>> list;
	for (int i = 0; i < N; ++i)
	{
		int temp = 0;
		cin >> temp;
		list.push(temp);
	}

	int result = 0;
	while (list.size() != 1)
	{
		int cardA = list.top();
		list.pop();
		int cardB = list.top();
		list.pop();
		list.push(cardA + cardB);
		result += cardA + cardB;
	}

	cout << result;

	return 0;
}

근데 최근에 삽입정렬을 보아서 문득 든 생각이였는데

어차피 최소값 두개를 합쳐서 그 값을 다시 넣는걸 반복하는거면

처음에 값을 받고 퀵정렬로 정렬 후에 연산을 하면 거의 정렬 된 상태이니까 삽입정렬도 메리트 있지 않을까? 생각했다.

결과는 정답은 나오지만 시간초과였다

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

void Swiching(int & a, int & b)
{
	int temp = a;
	a = b;
	b = temp;
}

void InsertionSort(vector<int> & numList, int size)
{
	for (int i = 1; i < size; ++i)
	{
		for (int j = i; 0 < j; --j)
		{
			if (numList[j] < numList[j - 1])
			{
				Swiching(numList[j - 1], numList[j]);
			}
		}
	}
}

int main()
{
	int N;
	cin >> N;

	vector<int> list;
	for (int i = 0; i < N; ++i)
	{
		list.push_back(0);
		cin >> list[i];
	}

	sort(list.begin(), list.end());

	int result = 0;
	for (int i = 0; i < N - 1; ++i)
	{
		list[i + 1] = list[i] + list[i + 1];
		result += list[i + 1];
		InsertionSort(list, N);
	}

	cout << result;

	return 0;
}

이렇게 업데이트 되는 배열속에서 최대, 최소값을 계속 확인해야하는 상황이라면

일단은 우선순위 큐를 사용하는게 빠르다고 느꼈다 =~=

#include <iostream>
using namespace std;

typedef int integer;

void Merge(integer * arr, integer * temp, int start, int mid, int end)
{
	for (int i = start; i <= end; ++i)
	{
		temp[i] = arr[i];
	}

	int part1 = start;
	int part2 = mid + 1;
	int index = start;

	while (part1 <= mid && part2 <= end)
	{
		if (temp[part1] <= temp[part2])
		{
			arr[index] = temp[part1];
			++part1;
		}
		else
		{
			arr[index] = temp[part2];
			++part2;
		}
		++index;
	}

	for (int i = 0; i <= mid - part1; ++i)
	{
		arr[index + i] = temp[part1 + i];
	}
}


void MergeSort(integer * arr, integer * temp, int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		MergeSort(arr, temp, start, mid);
		MergeSort(arr, temp, mid + 1, end);
		Merge(arr, temp, start, mid, end);
	}
}

void MergeSort(integer * arr, const int & size)
{
	integer * temp = new integer[size];
	MergeSort(arr, temp, 0, size - 1);
}


int main()
{
	int many = 0;
	cin >> many;
	
	integer * num = new integer[1'000'000];
	for (int i = 0; i < many; ++i)
	{
		cin >> num[i];
	}
	MergeSort(num, many);
	for (int i = 0; i < many; ++i)
	{
		cout << num[i] << '\n';
	}
}

퀵정렬로도 풀어지는 문제지만

N^2의 경우를 생각해서 N log N을 보장하는 병합정렬로 풀었다.

이번에 숫자 정렬자(digit separator)를 처음 알게됐는데 앞으로 자주 써야겠다. 보기 훨씬 편한듯ㅎㅎ

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
using namespace std;
typedef int integer;

int main()
{
	string N;
	cin >> N;

	integer tempInt = 0;
	for (const char & data : N)
	{
		tempInt += data - '0';
	}

	if (tempInt % 3 == 0)
	{
		sort(N.begin(), N.end(), greater<>());
		if (N[N.length() - 1] == '0')
		{
			cout << N;
			return 0;
		}
	}
	cout << "-1";
	return 0;
}

좀 오래 걸렸었는데 그만큼 배우는게 있었다

1. 일단 문제 파악을 처음에 잘못했다

들어오는 N이 100,000 이하 라고 처음에 이해를 해버려서 처음엔 Out of range가 났었다.

자리수가 100,000 이하 였던 것.. =_=

굉장히 큰 수이므로 정수로 해결하던 부분을 문자열로 해결하는 방식으로 변경했다.

2. 복잡한 방식 채택

그 후에는 시간 초과가 났었는데

그 이유는 불필요한 for문을 사용했었다.

30의 배수가 되려면 각 자리의 합이 3의 배수이고 마지막 자리가 0이면 순서가 어떻든지 가능한 조건이였다.

근데 나는 내림차순으로 정렬하여 prev_permutation 을 사용하면서 매번 3, 2, 5 로 나눈 값이 0인지 확인하였는데

이부분이 시간 초과의 범인이였다

3.  잘못알고 있었던 atoi

입력을 123을 한다면

처음엔 예상 값이 그대로

1

2

3

이 나올줄 알았는데

123

23

3

이 나온다..

주소를 받아 integer가 아닌 문자가 나올때까지 읽기때문에 이러한 값이 나왔다..

그래서 '0'을 빼주어 integer로 변환 시켜 주었다.

4. 새로 알게 된 사용법

생각해보면 string은 char의 집합이고 char또한 정수형이기 때문에 sort함수를 이용할수 있지 않을까 해서

실행해봤는데 잘 됐다

그리고 시간초과가 나와서 여러가지 보다가

cout의 endl이 개행문자 출력과 함께 출력버퍼를 비우는 역할을 하기에 시간을 좀 먹는다고 한다.

'\n'을 통해 개행을 해야겠다.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main()
{
	int N;
	cin >> N;

	vector<int> ropeList;
	
	for (int i = 0; i < N; ++i)
	{
		int rope = 0;
		scanf("%d", &rope);
		ropeList.push_back(rope);
	}

	sort(ropeList.begin(), ropeList.end(), greater<>());

	int maxW = 0;
	for (int i = 0; i < ropeList.size(); ++i)
	{
		int temp = ropeList[i] * (i + 1);
		if (maxW <= temp) maxW = temp;
	}
	cout << maxW;
	return 0;
}

분명 맞다고 생각했는데 여러번 틀렸다

틀린 부분은 저 마지막 for문에서 최대값 구하는 부분인데

이전 코드에서는 최대값이 아니면 바로 끝냈기 때문.

"5 1 1 1 3 1" 같은 입력값을 예로 들면

먼저 내림차순을 한다. 3 1 1 1 1 (5는 로프 개수 이므로 제외)

3 최대 3

1 최대 2

나는 여기서 멈추었었는데 끝까지 가보면

1 최대 3

1 최대 4

1 최대 5

으로 최대 중량 5를 구할 수 있다.

이러한 끝까지 생각해야하는 문제도 신경써야겠다.!

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

void GetNum(const string & str, vector<int> & numList)
{
	string element;
	for (const auto & data : str)
	{
		
		if (data == 43 || data == 45)
		{
			numList.push_back(stoi(element));
			element = data;
		}
		else element += data;
		
	}
	numList.push_back(stoi(element));
}

int main()
{
	string input;
	cin >> input;

	vector<int> numList;
	GetNum(input, numList);
	
	int result = 0;
	bool transSwitch = false;
	for (auto & data : numList)
	{
		if (data < 0) transSwitch = true;
		if (transSwitch == true && 0 < data) data *= -1;
		result += data;
	}

	cout << result;

	return 0;
}

내가 푼 코드는 이러하다.

그리디 유형에 속해 있어서 그리디적으로 생각해보려고 했다.

수식 맨 처음부터 읽으면서 당장 '-'가 나온다면 그 후에 나오는 +는 모두 -로 바꾸어 계산하였다

input을 하나하나 읽으면서 동시에 result로 계산하는 방법이 더 나았지만

길이제한없는 연속된 정수를 따로 저장해보고 싶어서 저장하는 함수를 따로 구현하였다.

근데 다른 사람이 푼 코드가 충격이였다

#include <stdio.h>

int main()
{
  char cmd;
  int n,s,m=0;
  for(scanf("%d",&s);scanf("%c",&cmd),cmd!=10;)
  {
    if(cmd=='-')m=1;
    scanf("%d",&n);
    if(m)s-=n;
    else s+=n;
  }
  printf("%d",s);
  return 0;
}

ㅋㅋㅋㅋ보면서 대단하다고 생각했다

다음에 기회가 된다면 응용해 봐야겠다

정말 만만하게 봐서 설계 대충 하다가 정말 오래 걸렸던 문제ㅠ

처음에는 정말 길게도 풀었다.

#include <bits/stdc++.h>

using namespace std;

void tokenizerTimeformat(vector<string> & time, bool & isAm, string & str)
{   
    string tempStr = str;
    const string delimiter = ":";
    size_t pos = 0;
    
    string tempdegit ="";
    for (int i = 0; i < str.length(); ++i)
    {
        if(isdigit(str[i]) == 0)
        {//is character not degit
            if(tempdegit.length() != 0)
            {
                time.push_back(tempdegit);
                tempdegit = "";
            }
        }
        else 
        {
            tempdegit += str[i];
        }
    }
    
    if (tempStr[8] == 'A') isAm = true;
    if (tempStr[8] == 'P') isAm = false;
}


string timeConversion(string s) 
{
    vector<string> time_s(0);
    vector<int> time_i(0);
    bool isAm = false;
    tokenizerTimeformat(time_s, isAm, s);
    cout<<"isAM : "<<isAm<<endl;

    for(auto data : time_s)
    {
        time_i.push_back(stoi(data));
    }

    if(isAm == false)
    {//isPM
        time_i[0] += 12;
        if (24 <= time_i[0])
        {
            time_i[0] -= 12;
        }
    }
    if(isAm == true)
    {
        if (12 <= time_i[0])
        {
            time_i[0] = 0;
        }
    }
    
    time_s[0] = to_string(time_i[0]);
    if(time_s[0].length() < 2)
    {
        time_s[0] = "0" + time_s[0];
    }
    
    return time_s[0] + ":" + time_s[1] + ":" + time_s[2];
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string s;
    getline(cin, s);

    string result = timeConversion(s);

    fout << result << "\n";

    fout.close();

    return 0;
}

그러다가 scanf를 이렇게 사용할수도 있구나를 알게 돼서 적용하여 풀어보니까 정말 쉽게 풀렸다 =~=

규칙 있는 문자열을 입력받아 나눌 때 편하게 사용할 수 있을 것 같다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
   int h, m ,s;
   char c;
   scanf("%d:%d:%d%c",&h ,&m ,&s, &c);
   
   if(c == 'A' && h == 12)
   {
       h = 0;
   }
   if(c == 'P')
   {
       if (h < 12) h += 12;
   }

   printf("%02d:%02d:%02d",h,m,s);
   return 0;
}