문제링크
https://www.acmicpc.net/problem/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를 출력한다.
해석
입력받는 수를 string으로 받고 각 위치를 나눠가면서 계산하고 만약 앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같다면 YES를 출력해준다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
// 유진수 파악
void yujin(string n) {
int size = n.size();
int* arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = n[i] - '0';
}
int fir = 1;
int sec = 1;
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j <= i; j++) {
fir = fir * arr[j];
}
for (int j = i + 1; j < size; j++) {
sec = sec * arr[j];
}
if (fir == sec) {
cout << "YES" << '\n';
return;
}
fir = 1;
sec = 1;
}
cout << "NO" << '\n';
}
int main() {
string n;
cin >> n;
yujin(n);
}
|
cs |
Memo
string을 이용할 지 int를 이용할 지 굉장히 고민을 많이했고 결국 string을 사용하여 풀이했다.
첫번째 for문에서 i가 size-1보다 작을때까지 진행해야 한다. 그래야 오른쪽에서도 한 자리가 남아있을 수 있다. 이것을 모르고 첫 제출에서 for(int i=0; i < size; i++)로 for문 범위를 잡아서 99%에서 틀렸다.
예외 케이스는 1인 것 같다. 1일 때 수를 나눌 수 없기 때문에 유진수가 아닌데 위처럼 for문의 범위를 설정하면 yes가 출력 된다.