분해합의 개념)
어떤 자연수 N이 있을 때, N의 분해합은 N+각 자리수의 합입니다.
예를 들어, 198의 분해합은 198 + 1 + 9 + 8 = 216 입니다.
이때 198은 216의 생성자라고 합니다.
문제 풀기 전 생각)
N이 백만 이하의 자연수이므로 1부터 하나하나 검사를 하기에는 시간이 너무 오래 걸릴 것 같습니다.(주어진 시간도 2초로 짧습니다.)
분해합은 생성자와 각 자리수를 모두 더한 것인데, 각 자리수가 될 수 있는 가장 큰 값은 9입니다.
그러므로, 분해합-자리수*9 를 한 수가 생성자 될 수 있는 최솟값이 되는 것이죠.
예를 들어 주어진 분해합이 256일 때 우리는 256 - 3*9 = 229 부터 검사를 하면 되는 것입니다.
풀이)
1. 먼저, 분해합을 입력받아 몇 자리수인지 구합니다.
자리수를 구하기 위해서는, 10으로 몇 번 나누어야 0이 되는지를 구하면 됩니다.
987654 인 경우, 987654(0번)->98765(1번)->9876(2번)->987(3번)->98(4번)->9(5번)->0(6번)
10으로 6번 나누었을 때, 0이 되므로 6자리 수인 것을 알 수 있습니다.
저는 이렇게 N의 값을 M에 대입한 후 0이 될 때까지 10으로 나누어 자리수를 구했습니다.
int check = 0; //추후에 생성자가 있는지 없는지 판별하는데 사용할 변수
int N = 0;
scanf("%d", &N);
int M = N;
// 자리수 계산
int count = 0;
while (M)
{
M /= 10;
count++;
}
2. 이제 자리수를 구했으니 생성자를 구할 차례입니다.
저는 각 자리수를 더하는 계산이 편하도록 배열을 만들고 각 자리수를 하나씩 넣었습니다.
그리고 각 자리수들과 생성자인지 판별할 수를 더해 sum 이라는 변수에 넣고,
sum 이 처음에 우리가 입력한 N과 같은지 판별하도록 하였습니다.
//1번에서 구한 자리수를 이용하여 탐색 시작
int start = N - 9 * count;
for (int i = start; i < N; i++)
{
//배열에 각 자리수 저장
int number[6] = {0};
for (int j = 0; j < count; j++)
{
number[j] = (int)(i / pow(10, j)) % 10;
}
//각 자리수들과 i를 더해서 분해합과 같은지 비교
int sum = 0;
sum = number[0] + number[1] + number[2] + number[3] + number[4] + number[5] + i;
if (sum == N)
{
printf("%d\n", i);
check = 1;
break;
}
}
//생성자가 존재하지 않으면 0 출력
if (check == 0)
printf("0\n");
전체 코드)
#include <stdio.h>
#include <math.h>
int main(void)
{
int check = 0; // 생성자가 있는지 확인할 변수
int N = 0;
scanf("%d", &N);
int M = N;
// 자리수 계산
int count = 0;
while (M)
{
M /= 10;
count++;
}
// 생성자 범위를 최소화하여 탐색 시작
int start = N - 9 * count;
for (int i = start; i < N; i++)
{
int number[6] = {0};
for (int j = 0; j < count; j++)
{
number[j] = (int)(i / pow(10, j)) % 10;
}
int sum = 0;
sum = number[0] + number[1] + number[2] + number[3] + number[4] + number[5] + i;
if (sum == N)
{
printf("%d\n", i);
check = 1;
break;
}
}
if (check == 0)
printf("0\n");
return 0;
}
결과)
위 방법으로 제출하니 시간도 0ms 로 빠른 것을 확인할 수 있습니다.
'백준 > c' 카테고리의 다른 글
백준_15829_Hashing (0) | 2024.04.23 |
---|---|
백준_2525_오븐시계 (0) | 2024.04.23 |
백준_10926_??! (0) | 2024.04.23 |
백준_2798_블랙잭 (0) | 2024.04.22 |
백준_2292_벌집 (0) | 2024.04.22 |