[C++]백준(BOJ) 1356번 유진수 문제풀이

문제 링크 : https://www.acmicpc.net/problem/1356

문제

유진수는 어떤 수를 10진수로 표현한 뒤 그 수를 두 부분으로 나눴을 때, 앞부분 자>리수의 곱과 뒷부분 자리수의 곱이 같을 때를 말한다.
예를 들어, 1221은 유진수이다. 12와 21로 나눴을 때, 앞부분 자리수의 곱 12는 >뒷부분 자리수의 곱 21과 같기 때문이다.
1236도 마찬가지로 유진수이다. 하지만, 1234는 아니다. 수를 나눌 때 항상 연속 >된 자리수를 나눠야하고, 각 부분에 적어도 한자리는 있어야 한다.
예를 들어, 12345는 총 4가지 방법으로 나눌 수 있다. 1-2345, 12-345, 123-45, >1234-5
어떤 수 N이 주어질 때, 이 수가 유진수인지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수 N이 주어진다. 이 수는 2,147,483,647보다 작거나 같은 자연수이다.

예제 입력,출력

알고리즘 분류

• 수학
• 구현
• 문자열
• 브루트포스 알고리즘
• 사칙연산

해설

어떤 수가 ‘유진수’ 이려면 해당 수를 피벗을 기준으로 좌, 우 두 덩어리로 나누었을 때 각 덩어리 각각의 숫자 간의 곱이 같은 경우가 존재해야 한다.
이때 같은 경우가 단 한 개라도 존재한다면 유진수라고 판별할 수 있다.
예를 들어 예제 입력1 ‘1236’의 경우 3과 6 사이를 피벗으로 설정할 때, 1x2x3 == 6 이므로 1236은 ‘유진수’라고 판별할 수 있다.
하지만 예제 입력 4 ‘4729382’의 경우 어떤 위치를 피벗으로 설정하던 좌, 우 덩어리 각 숫자의 곱이 같은 경우가 존재하지 않으므로 ‘유진수’ 가 아니다.
단 예제입력 2 ‘1’과 같은 한자리 수의 경우 좌, 우 덩어리로 나눈다 라는 것 자체가 불가능하므로 ‘유진수’가 아니다.
이를 해결하기 위해 수를 입력받고 각 자릿수마다의 숫자를 다뤄야하기 때문에 문자열로 변환한 후, 브루트포스 알고리즘으로 가능한 피벗의 경우를 전부 탐색하여 좌, 우 덩어리 곱이 같은지 검사하여 유진수인지 판별한다.

소스코드

// 브루트 포스 알고리즘으로 해결
#include <iostream>
#include <string>

using namespace std;

int main() {
	// 입력받을 수
    int N;
	cin >> N;
	// 문자열로 바꿔서 해결
	string str = to_string(N);

	// 나누는 부분을 한칸씩 왼쪽에서 오른쪽으로 이동
	for (int i = 1; i < str.size(); i++) {
		// 곱하기 연산을 위해 결과값 1로 초기화
		// 왼쪽 부분
		int res1 = 1;
		// 오른쪽 부분
		int res2 = 1;
		// 왼쪽 부분 계산(res1)
		for (int j = 0; j < i; j++) {
        // char -> int 변환하여 계산결과 업데이트 
			res1 = res1 * (str[j] - '0');
		}
		// 오른쪽 부분 계산(res2)
		for (int k = i; k < str.size(); k++) {
			res2 = res2 * (str[k] - '0');
		}
		// 왼쪽, 오른쪽 곱이 같다면 유진수
		if (res1 == res2) {
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
	return 0;
}