나머지와 몫이 같은 수

문제

언어

  • JavaScript

순서도

  1. 수학 공식 도출
  2. 공식을 이용한 계산

문제 풀이 step 1

  • N 으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 문제입니다.
  • 예를 들어 N = 3 일 때, 모든 경우는
    • 4 (3 * 1 + 1)
    • 8 (3 * 2 + 2)
    • 이렇게 두 가지가 있습니다.
  • 다른 예로 N = 5 일 때, 모든 경우는
    • 6 (5 * 1 + 1)
    • 12 (5 * 2 + 2)
    • 18 (5 * 3 + 3)
    • 24 (5 * 4 + 4)
    • 이렇게 네 가지가 있습니다.
  • 위의 예시를 보면서 모든 경우의 합을 공식으로 나타낼 수 있습니다.
    • 바로 (N * 1 + 1) + (N * 2 + 2) + (N * 3 + 3) + ... + (N * (N - 1) + (N - 1)) 입니다.
    • 이를 좀더 정제하면 (N + 1) * ((N - 1) * (N)) / 2 과 같은 식이 됩니다.
  • 이렇게 도출한 식을 이용해서 계산하면 정답이 나옵니다.
  • 단, 문제에서 주어진 N 의 범위가 상당히 크기 때문에 BigInt 형을 사용해야 합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 이번 문제도 다른 분들의 풀이에 비해 제 풀이가 소요 시간이 긴 것을 확인한 후에 공식으로 만드는 과정을 거쳤습니다.
  • 다른 분의 풀이의 소요 시간과 비교하지 않고, 바로 공식을 만들어보는 실력을 갖출 수 있으면 좋겠습니다.
  • “반복문을 어떻게든 처리해서 생략할 수 는 없을까?” 라는 의문을 가져보는 것도 좋을 것 같습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	// BigInt 형으로 계산
	const n = BigInt(input[0]);
	// 공식 사용
	return ((((n - 1n) * n) / 2n) * (n + 1n)).toString();
};

console.log(solution(input));