[백준] 4375번 : 1 (C++)

4375번: 1

📚 문제 한 줄 요약

1로만 이루어진 n의 배수 중 가장 작은 자릿수 찾기

 

📚 고민한 부분

1. 입력이 언제가 마지막인지 알 수 없는데 어떻게 입력받아야 할까?

  이 부분은 예전에 같은 유형은 겪은 적이 있어서 쉽게 해결했다. 아래 링크의 문제 풀이를 참고하였다.

  ▶ https://nhee-devlog.tistory.com/2

 

2. 자릿수를 늘린 수열 값을 그대로 저장하면 변수 최대 크기를 넘기는데 어떻게 처리해야 할까?

  이는 mod값을 이용하는 걸로 해결하였다. 자세한 내용은 풀이에서 다루었다.

 

 

📚 풀이 (핵심 : 어떻게 1로만 이루어진 n의 배수를 구하는 식을 짤 것인가)

위 고민한 내용을 바탕으로 다음과 같은 순서로 코드를 작성했다.

문제 해결 순서는 다음과 같다.

1. 입력 데이터 받기
2. 1로만 이루어진 n의 배수 구하기 (최솟값이므로 구함과 동시에 프로그램 종료)
3. 위에서 구한 값 출력하기

입력과 출력은 어렵지 않으므로 2번 과정만 설명을 덧붙이겠다.

 

1로만 이루어진 n의 배수 구하기

		int mod = 1; // mod of sequence of 1
		int digit = 1;
		
		// 2. Get digits of smallest such a multiple of n
		while (true) {
			if (mod%n == 0)
				break;
			else {
				mod = (mod*10+1)%n;
				digit++;
			}
		}

mod에 1로만 이루어진 수열 중 가장 작은 값인 1로 초기화하여 시작한다.

만약, n으로 나누었을 때 나머지가 없다면 n의 배수이므로 탐색을 종료한다.

그렇지 않다면, 더 큰 1로만 이루어진 수열이 n의 배수인지 확인해 보아야 한다.

현재 수열이 배수가 아닐 때 현재 값에서 다음으로 큰 1로만 이루어진 수열의 식은 다음과 같다.

 

(현재 1로만 이루어진 수열)*10+1

 

하지만 이대로 값을 저장하면 변수 최대 크기를 초과하게 되므로 mod값을 이용해줘야 한다.

따라서 ((현재 1로만 이루어진 수열)*10+1)%n 식으로 더 큰 1로만 이루어진 수열이 배수인지 확인한다.

mod값에 다시 mod를 하든 원래 값에서 mod를 하든 그 값은 같음을 이용한 것이다.

 

📚 전체 Code