백준_4375번 1 (문제 이름임)

phoenixKim·2022년 5월 25일

백준 알고리즘

목록 보기

31/174

알아야 할점.

1) 입력값이 계속해서 주어질 때
while(cin >> 변수) 로 하면 됨.

교안의 입력의 끝을 정하지 ~~ 참고하자.

2) 모듈러 연산, 나머지 연산
: 맨 밑에 있음.

모듈러 연산의 의미

큰수를 작은 수로 만드는 것임.

최근 추가 231126 일요일

왜 모듈러를 사용해도 되는지??
-> 지금의 경우, 어차피 찾으려고 하는 값은 주어진 n으로 나눌수 있는 특성을
가지고 있기 때문에 값을 커진 후에도 바로 모듈러가 가능하다는 것을 생각해 내야 함!

첫번째 코드

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

int main()
{
	// 3 -> 111
	// 7 -> 111111

	// n에다가 * 10 + 1만큼식 진행을 하면서, 
	// 입력되는 n과의 나머지 계산을 진행하면서 0이 나올때의
	// 최소값을 구하는 방식으로 하면되지 않을까? 생각을 함. 

	
		
		int input;
		

		while (cin >> input)
		{
			int cnt = 0;
			long long n = 1;

			while (1)
			{
				if (n % input == 0)
				{
					
					// 자릿수를 구해야 함.
					while (n != 0)
					{
						n /= 10;
						++cnt;
					}
					cout << cnt << endl;
					break;
				}
				else
					n = n * 10 + 1;

			}
			
		}
		
	
}

-> 시간 초과 발생함.

고찰
: 모듈러 연산을 하지 않아서 시간 초과 발생!

최종 코드

: 모듈러 연산을 하지 않으면, 틀리게 되어 있음.

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

int main()
{
	// 3 -> 111
	// 7 -> 111111

	// n에다가 * 10 + 1만큼식 진행을 하면서, 
	// 입력되는 n과의 나머지 계산을 진행하면서 0이 나올때의
	// 최소값을 구하는 방식으로 하면되지 않을까? 생각을 함. 

	
		
		int input = 0;
		

		while (cin >> input)
		{
			int cnt = 1;
			long long n = 1;

			while (1)
			{
				if (n % input == 0)
				{				
					
					cout << cnt << endl;
					break;
				}
				else
				{
					n = n * 10 + 1;
					// 여기서 한줄을 더 추가해야 함.
					n %= input;
					++cnt;
				}

			}
			
		}
		
	
}