오각형, 오각형, 오각형…

문제

백준 1964번 - 오각형, 오각형, 오각형…

언어

JavaScript

순서도

각 단계의 오각형을 살펴보며 규칙 혹은 공식 찾기
찾은 규칙이나 공식에 따라서 N 단계의 오각형의 점의 개수를 45678 로 나누고 출력

문제 풀이 step 1

우선, 각 단계를 분석하고, 그려가며 규칙 또는 공식을 찾습니다.
저는 두 가지 방법으로 풀었습니다.
첫 번째는 다이나믹 프로그래밍 방식으로 해결했습니다.
- 1 단계: 1 + 1 + 1 + 2
- 2 단계: 1 단계 + 2 + 2 + 3
- 3 단계: 2 단계 + 3 + 3 + 4
- 위처럼 전 단계에 추가로 현 단계 * 3 + 1 씩 늘어납니다.
- 이를 식으로 나타내면, dp[n] = dp[n - 1] + 3 * n + 1 과 같은 식을 구할 수 있습니다.
점화식을 이용해서 각 단계마다 오각형의 개수를 구하고, 45678 로 나눠가며, dp 배열을 채우고, dp[n] 을 출력하면 정답입니다.

문제 풀이 step 2

풀이를 제출하고 나서, 제 풀이의 소요 시간보다 다른 분들의 풀이의 소요 시간이 상당히 적다는 것을 확인할 수 있었습니다.
그래서 혹시 한 번에 구하는 공식이 있으려나 라는 생각에 다시 살펴보니, 공식을 찾아 낼 수 있었습니다.
- 위 사진을 살펴보시면, 각 단계마다 오각형을 3 등분 시켜놓았습니다.
- 3 단계를 예시로 들어서 설명하자면,
  - 가장 왼쪽의 1 등분은 1 + 2 + 3
  - 가운데 1 등분은 1 + 2 + 3
  - 가장 오른쪽의 1 등분은 1 + 2 + 3 + 4 입니다.
  - 이를 다 더하면 (1 + 2 + 3) * 3 + 4 입니다.
  - 이를 공식으로 나타내면 3 * i * (i + 1) / 2 + i + 1 입니다.
위 과정을 통해서 구한 공식으로 n 번째 단계의 오각형의 개수를 구하고, 45678 로 나눈 후에 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

이런 유형의 문제는 보통 이전의 값을 이용해서 점점 키워가는 다이나믹 프로그래밍 기법으로 풀립니다.
그래서 이번에도 그런 방식으로 풀었지만, 틀에 박힌 아주 진부한 풀이였습니다.
틀에 박히지 않고, “공식을 만들어볼 수 있나?” 라는 생각을 할 수 있게 되었으면 해서 포스트하게 되었습니다.

소스 코드 1

// 다이나믹 프로그래밍 기법으로 푸는 방법
const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const MOD = 45678;
	const n = Number(input[0]);

	// base
	const dp = [0, 5];
	for (let i = 2; i <= 10000000; i++) {
		// 점화식 적용
		dp[i] = dp[i - 1] + 3 * i + 1;
		// 매번 45678 로 나머지 연산 수행
		dp[i] %= MOD;
	}

	return dp[n];
};

console.log(solution(input));

소스 코드 2

// 공식을 이용해서 한 번에 구하는 방법
const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const MOD = 45678;
	let n = Number(input[0]);

	// 미리 나머지 연산을 수행해도, 결과는 동일
	// 이렇게 하면 Number 가 표현할 수 있는 범위를 넘어가지 않을 수 있음
	n %= MOD;
	// 공식 적용
	return (n + 1 + (3 * n * (n + 1)) / 2) % MOD;
};

console.log(solution(input));