[백준/JS] 4375번 - 1

Pakxe·2024년 1월 8일

JavaScript baekjoon ps

PS

목록 보기

1/16

✦ 문제

(링크: https://www.acmicpc.net/problem/4375)

✦ 모듈러 분배 법칙

이 문제를 풀려면 모듈러 연산의 분배 법칙에 대하여 알아야 한다. 어려운 법칙은 아니고 아래 공식을 받아들이면 된다(증명은 따로 검색해보길..).

덧셈, 뺄쎔, 곱셈에 대해선 위 분배 법칙이 성립하지만, 나눗셈의 경우 다른 분배법칙이 존재하니 필요해진다면 찾아보도록 하자.

❌ 안되는 풀이

일단 자연스러운 생각의 흐름대로 1, 11, 111들을 주어지는 수로 나눠 나머지를 구하는 방법이 있다.

다만 이 방법은 오버플로가 날 가능성이 매우 높다. 왜냐면 예제로 주어지는 입력을 보면 9991이 12개의 1에서 나머지가 0이라고 했는데, 12개의 1은 일단 천억이다. js는 아니지만 c++의 int자료형은 21억이 최대 수용 가능한 수이기 때문에 이 방법은 틀릴 확률이 높다.

⭕️ 맞는 풀이

안되는 풀이가 안되는 이유(?)는 일단 나눠져야 하는 1111...의 자릿수가 매우 커질 수 있기 때문이다. 이 나눠져야 하는 수가 자료형에 담겨야하는데 여기서부터 문제가 될 수 있다.

그러면 자연스럽게 앞에서 배운 분배법칙을 사용하면 되는데, 앞으로 분배 법칙은 결과 값을 특정 숫자로 나눈 나머지 구하기에서 사용하면 편하다.

분배 법칙을 사용하면 엄청 커다란 수 % n -> 그것보단 작은 수 % n * 그것보단 작은 수 % n 으로 구할 수 있단 장점이 있다. 그것보단 작은 수는 당연히 자료형에 담길 만큼의 작은 수가 된다. 그렇게 구해진 그것보단 작은 수 % n 은 0 ~ n - 1사이의 범위를 갖고, n은 1 ~ 10000사이의 값이기 때문에 당연하게 자료형에 들어갈 수 있게 된다.

예시로 주어진 7을 사용해 어떻게 오버플로 없이 계산할 수 있을지 흐름을 생각해보자. 7은 주어진 답으론 6자리의 1을 나머지 없이 나눌 수 있다고 되어있다.

이때 11, 111 은 각각 1*10+1 , 11*10+1 임을 이용해서 분배 법칙에 적용하게 된다. 그리고 111 % 7 로 나온 나머지 값을 다시 % 7을 해준다 해도 값이 변하지 않는 면을 이용한다. (a % m = b = b % m)

이해를 위해 1111까지 작성했지만 각 과정은 거의 유사하다.

형광펜(동그란 색)으로 표시한 부분을 보면 결국 현재 값은 이전에 구한 값을 이용한다는 점을 알 수 있다.

이를 점화식으로 표현한다면, 아래처럼 만들 수 있다.

이 식을 이용해 예제로 주어진 7을 생각해본다면 아래와 같은 과정을 따르게 된다.

     1 % 7 = 1
    11 % 7 = (1 * 10 + 1) % 7 = 4
   111 % 7 = (4 * 10 + 1) % 7 = 6
  1111 % 7 = (6 * 10 + 1) % 7 = 5
 11111 % 7 = (5 * 10 + 1) % 7 = 2
111111 % 7 = (2 * 10 + 1) % 7 = 0

이제 이 점화식을 이용해 코드를 작성해보자.

✦ 작성 코드

const answers = [];

for (let i = 0; i < nums.length; i++) {
  const cur = nums[i];
  let num = 1; // 이 변수에 이전에 구한 값이 담기게 되는 것
  let length = 1;

  while (1) {
    if (num % cur === 0) {
      answers.push(length);
      break;
    } else {
      num = (num * 10 + 1) % cur; // 점화식
      length += 1; // 1을 한자리 더 추가함
    }
  }
}

console.log(answers.join('\n'));