[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;
}