백준 4375번 1(C++)

문제

처음에 문제 이해가 잘 안됐다.

1로만 이루어졌다는게 무슨말인가 했는데 그냥 몇을 곱해서 1111 111111 11111111 이런식으로 만들라는 뜻이었다.

3의 경우 배수로 이뤄지는 가장 짧은 1로 이뤄진 수는 111 이라서 이렇게 나온다.

7인 111111 이런식

정답 코드

#include <iostream>

using namespace std;

int A;
long long result(long long n )
{
	if (n == 1 || A == 1)
		return (1);
	else
	{
		for (long long i =0;i < 10; i++)
		{
			if (((A * i) + n) % 10 == 1)
			{
				return (result(((A * i) + n)/10) +1);
			}
		}
	}
}

int main()
{
	while (cin >> A)
	{
		cout << result(0)<< "\n";
	}
}

문제 풀이의 흐름

• 그냥 보면 어떻게 풀어야 할까 싶지만 문제의 조건에서 2와 5로 나눠 떨어지지 않는다고 했다.

• 먼저 사람이 어떻게 이 문제를 푸는가를 먼저 접근해보았다.

• 만약 3의 경우 3 *7에 21 이고 제일 뒷자리가 1이 됐으므로 2만 남기고 다시 연산을 반복해준다.

• 이 과정이 계속 재귀적으로 일어난다.

• 문제가 풀린다.

주의 할 점

간단한 조건으로 풀 수 있는데 조건문으로 계속 분기하다 보면 답이 없이 코드가 복잡해진다.

일단 if문이 너무 많다고 생각이 들면 내가 접근하고 있는 알고리즘이 틀렸다고 생각하고 다시 푸는게 더 빠른 것 같다.

추가적으로 0을 곱하는 것을 못찾아서 꽤 오래걸렸는데 마지막 부분에 찾아서 for문의 시작을 0으로 해줬다.

반성 및 고찰

틀린코드

#include <iostream>

using namespace std;

long long A1;
long long A;
long long result(long long n,long long flag)
{
	if (n == 1)
		return (1);
	else
	{
		for (long long i =1;i < 10; i++)
		{
			if (flag == 1)
			{
				if (n*i %10 == 1)
				{
					A= A1%10;
					A1 /=10;
					return (result(n*i / 10, 0) + 1);
				}
			}
			else if (((A * i) + n) % 10 == 1)
			{
				A= A1%10;
				A1 /=10;
				return (result(((A * i) + n)/10,0) +1);
			}
		}
	}
}

int main()
{


	while (cin >> A1)
	{
		A = A1;
		if (A1 > 10)
			A = A1%10;
		cout << result(A1, 0)<< "\n";
	}
}

이번 문제는 손코딩의 중요성을 조금 더 깨닫게 해주었다.

개발새발 손코딩 ㅋㅋㅋ

Uploaded by N2T