떡 먹는 호랑이

문제

백준 2502번 - 떡 먹는 호랑이

언어

JavaScript

순서도

d 번째 날의 A 와 B 의 계수 구하기
A 에 1 ~ k 까지의 수를 넣고, 구한 A 와 B 의 계수를 곱해가며 B 값 구하기

문제 풀이 step 1

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있습니다.
욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내줍니다.
- 예를 들어,
- 첫쨰 날 떡을 1 개 주었고, 둘째 날에 떡을 2 개 주었다면,
- 셋째 날에는 1 + 2 = 3 개
- 넷째 날에는 2 + 3 = 5 개
- 다섯째 날에는 3 + 5 = 8 개
- …
입력으로 할머니가 넘어온 날과 그 날 호랑이에게 준 떡의 개수가 주어질 때, 첫 날과 둘째 날에 준 떡의 개수를 구하는 문제입니다.

문제 풀이 step 2

첫 날 준 떡의 개수가 A 이고, 둘쨰 날 준 떡의 개수가 B 라면,
- 셋째 날 준 떡의 개수는 A + B 입니다.
- 넷째 날 준 떡의 개수는 A + 2B 입니다.
- 다섯쨰 날 준 떡의 개수는 2A + 3B 입니다.
- 위 방식처럼 처음부터 더해가면 d 번째 날의 떡의 개수도 xA + yB 의 식으로 나타낼 수 있습니다.
- 몇 번째 날의 정보인 d 를 이용해서 반복문을 수행해가며 xA + yB 의 x 와 y 를 구합니다.
위 과정을 통해서 xA + yB = k 의 식을 구해낼 수 있습니다.
xA + yB = k 식을 이용해서 A 에 1 ~ k 까지의 수를 넣어가며, 식이 성립할 때의 A 와 B를 구하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

다이나믹 프로그래밍 기법과 브루트포스 기법을 이용해야 하는 수학 관련 문제였습니다.
한편, 호랑이가 아주 사악한 것 같습니다. 날이 갈수록 받는 떡의 개수가 너무 많아집니다.

소스 코드

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

const solution = (input) => {
	const [d, k] = input[0].split(" ").map(Number);

	// xA + yB 의 x 와 y 구하기
	const muls = [null, [1, 0], [0, 1], [1, 1]];
	for (let i = 3; i <= d; i++) {
		muls[i] = [
			muls[i - 2][0] + muls[i - 1][0],
			muls[i - 2][1] + muls[i - 1][1],
		];
	}

	// A 에 1 ~ k 까지의 수를 넣어가며,
	// xA + yB = k 의 식이 성립하는지 검사
	let [a, b] = [0, 0];
	for (let i = 1; i <= k; i++) {
		if ((k - muls[d][0] * i) % muls[d][1] === 0) {
			[a, b] = [i, (k - muls[d][0] * i) / muls[d][1]];
			break;
		}
	}

	return [a, b].join("\n");
};

console.log(solution(input));