모든 챌린지
어려움 0명 해결 정답률 0%

가장 긴 순환마디

한계값 이하의 d 중에서 1/d의 순환마디가 가장 긴 d를 찾습니다.

배우게 될 내용

  • 나머지로 나눗셈 과정을 시뮬레이션할 수 있다
  • 조회 테이블로 반복을 찾아낼 수 있다
  • 처음 나온 위치로 순환 길이를 구할 수 있다

문제

원문 보기 (영어)

단위분수 중에는 유한소수가 되는 것(1/4 = 0.25)도 있고, 끝없이 반복되는 순환소수가 되는 것도 있습니다. 1/6 = 0.1666...은 한 자리짜리 순환마디가, 1/7 = 0.142857142857...은 여섯 자리짜리 순환마디가 반복됩니다. d = 2, 3, ..., limit 중에서 1/d의 순환마디가 가장 긴 d를 찾으세요. 손으로 하는 나눗셈을 코드로 그대로 옮기면 됩니다. 같은 나머지가 다시 나오는 순간부터 숫자가 반복됩니다.

longest_recurring_cycle(limit) 함수를 구현하세요.

입력

limit: 시도할 가장 큰 분모입니다.

출력

순환마디가 가장 긴 d를 반환합니다. 유한소수의 순환마디 길이는 0입니다. 여러 d가 같으면 가장 작은 값을 반환합니다.

제약 조건

2 ≤ limit ≤ 2000

예시

예시 1
입력:
limit = 8

예상 출력:
expected = 7
입력:
long long limit = 8;

예상 출력:
long long expected = 7;
입력:
long limit = 8;

예상 출력:
long expected = 7;

설명

2부터 8까지의 순환마디 길이는 0, 1, 0, 0, 1, 6, 0이므로 답은 7입니다.

예시 2
입력:
limit = 5

예상 출력:
expected = 3
입력:
long long limit = 5;

예상 출력:
long long expected = 3;
입력:
long limit = 5;

예상 출력:
long expected = 3;

설명

1/3은 한 자리가 반복되고 1/2, 1/4, 1/5는 유한소수이므로 답은 3입니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

1/d의 새로운 자리는 나머지에 10을 곱한 값에서 나옵니다.

힌트 2

각 나머지가 처음 나온 단계를 기록해 두세요.

힌트 3

나머지가 0이 되면 유한소수입니다. 그렇지 않으면 같은 나머지가 두 번 나온 단계의 차이가 순환마디의 길이입니다.

예상 복잡도

시간 O(limit²), 추가 공간 O(limit)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.