백준/c

백준_2231_분해합

S0LL 2024. 4. 22. 15:54

2231번 문제 사진

 

분해합의 개념)

 어떤 자연수 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