[백준/C++] 28423번: 게임

문제

https://www.acmicpc.net/problem/28423

28423번: 게임

---

문제 요약

f(N)를 "N의 각 자릿수를 모두 더한 A와 N의 각 자릿수를 곱한 B를 이어 붙인 수" 라고 정의한다.

 

f(N), f(f(N)), f(f(f(N))), ... 형태로 계속 나아갈 때, f(x) = x 형태가 되는 x가 나올 수 있는지 알아내어 g(N)을 구할 수 있다.

 

f(x) = x가 나오게 된다면 g(N) = 1, 나올 수 없다면 g(N) = 0이다.

+ 단, f(N), f(f(N)), f(f(f(N))), ... 중에서 100000보다 큰 수가 하나라도 존재하면 g(N) = -1이다.

 

양의 정수 L, R이 주어졌을 때, g(L) + g(L + 1) + g(L + 2) + ... + g(R)의 값을 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

int L, R, res;

// checked[i]: f(N), f(f(N)), f(f(f(N))), ... 에 반환되는 값들을 저장하는 배열
bool checked[100001]; 

int g(int x) {
	
	// 이미 탐색했던 값이 한번 더 탐색된다면, 무한 반복
	// 즉 f(x) = x를 만족하는 x가 존재하지 않는다는 의미이므로 0 반환
	if (checked[x]) return 0;
	else checked[x] = true;

	int A = 0; // 각 자릿수의 합
	int B = 1; // 각 자릿수의 곱
	
	// A, B 구하기
	int tmp = x;
	while (tmp != 0) {
		A += (tmp % 10);
		B *= (tmp % 10);
		tmp /= 10;
	}

	// A, B 이어 붙이기	(C는 문제의 f(x)를 의미)
	int C = stoi(to_string(A) + to_string(B));

	// 100000보다 큰 수가 하나라도 존재하면 -1
	if (C > 100000) {
		return -1;
	}

	// f(x) = x가 하나라도 존재하면 1
	if (x == C) {
		return 1;
	}
	// f(x) = x가 아니라면 f(f(x)) = x를 만족하는 지 탐색
	else {
		return g(C);
	}
}

int main() {
	// 입출력 시간 단축
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> L >> R;

	for (int N = L; N <= R; N++) {
		res += g(N);
		memset(checked, false, sizeof(checked));
	}

	cout << res;

	return 0;
}

---

코드 설명

L, R을 입력 받고, 그 사이에 존재하는 수 N에 대해 g(N)를 호출한다.

 

N의 각 자릿수의 합 A, N의 각 자릿수의 곱 B를 구하고, string 형변환을 이용하여 이어붙인 C를 구한다.

+ C는 문제의 f(x)를 의미한다.

 

C가 100000보다 크다면 -1을 반환한다.

 

C가 f의 파라미터 x와 같다면, 즉 f(x) = x라면 1을 반환하고, 그렇지 않다면 f(C) 즉 f(f(x))를 탐색한다.

 

위 과정에서 f의 파라미터로 들어왔던 값을 checked 배열을 이용해 체크하고, 한번 더 들어온다면 f(x) = x인 경우가 없다는 의미이므로 0을 반환한다.

 

마지막으로, g(N)을 모두 더한 값을 출력한다.