[백준 - 1560] 비숍

||문제 이해

최대 70까지의 수가 아닌 최대 70자리의 수 N이 주어지고

N * N의 체스판에서 비숍을 놓을 수 있는 최대 개수를 구하라.

---

||해결 계획

70자리라는 숫자는 Unsigned long long으로도 담지 못한다ㄷㄷ

무조건 문자열을 이용하는 수 밖에 없다.

 

비숍을 놓을 수 있는 공식은 몇번 노가다를 해보면 간단히 알수 있다.

N + N - 2

 

이걸 문자열로 계산을 하면 된다.

---

||계획 검증

시간 복잡도에 경우 N의 각 자리를 탐색하는 반복문이 최대이기에

O(70)으로 충분히 가능하다.

---

||오답 원인

1. 70자리를 70까지의 수로 착각한것

2. 뺄셈을 계산할 때 첫 숫자가 0이면 지워지지 않고 출력 

---

||구현

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	string n; cin >> n;

	//1.Check One & Zero
	if (n == "0" || n == "1")
	{
		cout << n;
		return 0;
	}

	//2. Calculate n + n
	string ret;
	bool plus = false;
	while (0 < n.size())
	{
		int a = n.back() - '0';
		n.pop_back();

		a = plus ? a + a + 1 : a + a;
		plus = 9 < a ? true : false;

		ret += to_string(a % 10);
	}
	if (plus == true) ret += '1';

	//3. And then ret minus 2
	bool minus = false;

	int temp = ret.at(0) - '0' - 2;

	if (temp < 0)
	{
		minus = true;
		temp += 10;
	}
	ret.at(0) = temp + '0';
	
	int k = 1;
	while (minus == true)
	{
		temp = ret.at(k) - '0' - 1;

		if (0 <= temp)
		{
			ret.at(k) = temp + '0';
			break;
		}
		//음수일 때
		temp += 10;
		ret.at(k) = temp + '0';

		++k;
	}

	//3. Print
	if(ret.back() != '0') cout << ret.back();
	for (int i = ret.size() - 2; -1 < i; --i)
	{
		cout << ret.at(i);
	}
	return 0;
}

---

||되돌아보기

70자리수인걸 몰라봤던게 굉장히 아쉽다.

 

그 후에는 96%에서 계속 오답처리가 나오길래 예외를 생각해보았는데

해결했던게 0, 1처리였고 뺄셈을 계산했을 때 첫 자리가 0이면 제외되지 않는 경우가 있었다.

ex) N = 5 / result 08

 

시간은 한시간 정도 걸렸지만 예외도 잘 찾았고 끝까지 잘 풀어내서 좋았다.

---

||개선 코드

2를 빼는 부분을 더 간단하게 할 수 있을것 같아 줄여보았다.

//3. And then ret minus 2
	int k = 0;
	while (true)
	{
		if (k == 0) ret.at(k) -= 2;
		else ret.at(k) -= 1;

		//양수면
		if ('0' <= ret.at(k)) break;

		//음수일 때
		ret.at(k) += 10;
		++k;
	}

 

아래는 다른 분의 코드인데 주석을 달아 분석해봤다.

#include <stdio.h>
#include <string.h>

using namespace std;

int l;
char a[100];

int main() {
	int i;
	scanf("%s", &a);
	l = strlen(a);
	//0 ~ 2까지는 값이 똑같다.
	if (l == 1 && a[0] < '3') printf("%s", a);
	//그 나머지 부분
	else 
	{
		//문자열의 zero based 사이즈 구함
		l--;

		//문자열의 처음부터 끝까지 반복하며 정수화 함.
		for (i = 0; i <= l; i++)
		{
			a[i] -= '0';
		}

		//※1을 빼는 이유는 밑에서 *2를 해주기 위해서임.
		//문자열의 마지막 수에서 1을 뺀다.
		a[l]--;
		//size값 복사
		i = l;

		//뒤에서부터 처음까지 양수가 나올때까지 탐색한다.
		while (a[i] < 0) 
		{
			//음수이기에 앞의 자리에서 10을 빌려오는것.
			a[i] += 10;
			//탐색자리수를 먼저 땡겨주고, 빌려준 자리를 정산한다.
			a[--i]--;
		}

		//처음부터 끝까지 돌며 *2를 해준다.
		for (i = 0; i <= l; i++)
		{
			a[i] *= 2;
		}

		//*2를 한 결과에서 다음 자리 수에게 올려줄 수가 있으면 계산해준다.
		//중요한건 index 1까지만 계산한다.
		for (i = l; i >= 1; i--)
		{
			if (10 <= a[i])
			{
				a[i] -= 10;
				a[i - 1]++;
			}
		}

		//결과 출력
		//정수형으로 출력하기 때문에 위에서 마지막자리가 추가되도 가능했던것이다.
		for (i = 0; i <= l; i++)printf("%d", a[i]);
	}
}

나와 달리 더 간단한 방식과

문자열과 정수의 변환은 깔끔하게 두번 일어났다.

 

나도 이런 변환문제에 있을 때 최대한 변환을 적게하려는 고민에 중점을 두어봐야겠다.