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

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

1356번: 유진수

문제

유진수는 어떤 수를 10진수로 표현한 뒤 그 수를 두 부분으로 나눴을 때, 앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같을 때를 말한다.

예를 들어, 1221은 유진수이다. 12와 21로 나눴을 때, 앞부분 자리수의 곱 1*2는 뒷부분 자리수의 곱 2*1과 같기 때문이다. 1236도 마찬가지로 유진수이다. 하지만, 1234는 아니다. 수를 나눌 때 항상 연속된 자리수를 나눠야하고, 각 부분에 적어도 한자리는 있어야 한다.

예를 들어, 12345는 총 4가지 방법으로 나눌 수 있다. 1-2345, 12-345, 123-45, 1234-5 어떤 수 N이 주어질 때, 이 수가 유진수인지 아닌지 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 N이 유진수이면 YES, 아니면 NO를 출력한다.

예제 입력 1 복사

1236

예제 출력 1 복사

YES

---

이번 문제는 solved.ac https://solved.ac/

solved.ac

solved.ac에 의하면 브론즈1 에 속하는 문제이다.

하지만 개인적으로 B1의 난이도 치고는 상당히 까다로운 문제였다.

 

PS에 익숙하지 않은 사람이 이러한 문제를 처음으로 접하면 

바로 포기하게 만드는 수준의 문제였다.

 

문제를 간단히 Paraphrasing을 해보자면 

숫자 1236을 예로 들면 

1 / 2 * 3 * 6

1 * 2 / 3 * 6

1 * 2 * 3 / 6

 

한칸한칸 축(pivot)을 움직이면서 축을 기준으로 왼쪽 수들의 곱 오른쪽 수들의 곱이 같은 수라면 YES를 출력하는 문제이다.

1236은 1 * 2 * 3 == 6, 이렇기 때문에 YES를 출력해야한다.

 

또 다른 숫자를 예를 들자면

1234

1 / 2 * 3 * 4, 1 != 24

1 * 2 / 3 * 4, 2 != 12

1 * 2 * 3 / 4, 6 != 4

모두 다르기 때문에 NO를 출력하면 된다.

 

처음에 시도한 방법은 int로 입력받아서

%와 / 연산자를 이용해 한자리씩 나누어서 시도를 했는데 코드가 너무 길어지고 오류도 빈번히 발생해서

계속해서 생각해봤을 때 

역시나 비교하는 문제는 string, char로 진행하는 것이 가장 적합하다.

 

축(pivot) 변수를 이용해서 왼쪽 오른쪽 가르고 비교를 해야한다.

#include <iostream>
#include <string>

int main() {
    std::string num;  // 입력을 위한 string 변수 선언
    int left = 0, right = 0, pivot = 0; // pivot = 축
    bool ans = false; // YES, NO를 출력하기 위한 변수, false로 초기화
    std::cin >> num;  // 입력
    
    // num.size() - 1에 - 1을 한 이유는 마지막 숫자(digit)은 건드릴 필요가 없기 때문
    for(int i = 0; i < num.size() - 1; i++) {
        pivot++;     // pivot(축)을 1씩 증가
        left = 1;    // 왼쪽 수를 *로 저장하기 위해 1로 초기화, 0에 *를 하면 0이기 때문
        right = 1;   // 왼쪽과 마찬가지
        ans = false; // for문이 돌아갈 때마다 ans를 false로 초기화
        
        for(int j = 0; j < pivot; j++) // 축을 기점으로 왼쪽 수들을 곱하고 left변수에 저장
            left *= num[j] - '0'; // string이기 때문에 '0'(아스키코드 48)을 빼줘야 진짜 수가 나온다
            
        for(int k = pivot; k < num.size(); k++) // k를 pivot으로 초기화하고 pivot을 기준으로 오른쪽의 수들을 곱하고 right변수에 저장
            right *= num[k] - '0'; // 위에 left와 같은 원리
            
        if(left == right) { // left와 right의 수가 같다면 
            ans = true; // ans를 true로 설정하고
            break; // 더 이상 나누고 비교할 필요가 없기때문에 for문을 나간다
        }
    }
    
    // ans가 true라면 YES, 아니라면 NO를 출력한다.
    (ans == true ? std::cout << "YES\n" : std::cout << "NO\n");
    return 0;
}

---

#include <iostream>
#include <string>

int main() {
    std::string num;
    int left = 0, right = 0, pivot = 0;
    bool ans = false;
    std::cin >> num;
    for(int i = 0; i < num.size() - 1; i++) {
        pivot++;
        left = 1;
        right = 1;
        ans = false;
        for(int j = 0; j < pivot; j++)
            left *= num[j] - '0';
        for(int k = pivot; k < num.size(); k++)
            right *= num[k] - '0';
        if(left == right) {
            ans = true;
            break;
        }
    }
    
    (ans == true ? std::cout << "YES\n" : std::cout << "NO\n");
    return 0;
}