글 읽기 - 틀린거 같은데 왜 맞죠?

kcarollee 5년 전 0

n 자리수 계단수의 왼쪽 끝자리수에 뒤따라 올 수있는 수를 세서 digits 배열(n자리 계단수들 왼쪽 끝에있는 숫자의 수들)을 업데이트 해주면서 n+1자리 계단수의 수를 세는 방식입니다. temp_odd와 temp_even은 1012, 101, 1010101 과 같이 10이 따라 붙는 수를 처리해주기 위해서 활용한거고요. 그런데 temp_odd와 temp_even은 따로 MOD 처리 안해주고 그냥 순전히 digits 배열안에 들어갈 수들만 MOD처리 해줬는데도 맞는게 이상하네요

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000000

void copy(long long int *a, long long int *b)
{
    for (int i = 0; i < 9; i++){
        *(a + i) = *(b + i);
    }
}

void next_arr(long long int *arr, long long int *tmp)
{
    for (int i = 0; i < 9; i++){
        if (i == 0){
            *(tmp + 1) += *(arr) % MOD;
        }
        else if (0 < i && i < 8){
            *(tmp + i - 1) += *(arr + i) % MOD;
            *(tmp + i + 1) += *(arr + i) % MOD;
        }
        else if (i == 8){
            *(tmp + 7) += *(arr + 8) % MOD;
        }
    }
    copy(arr, tmp);
}

long long int sum(long long int *arrr)
{
    long long int sum = 0;
    for (int j = 0; j < 9; j++){
        sum += *(arrr + j);
    }
    return sum;

}

int main()
{
    long long int digits[9] = {2, 2, 2, 2, 2, 2, 2, 2, 1};
    long long int *temp;
    long long int temp_odd = 1, temp_even = 2;
    temp = calloc(9, sizeof(long long int));
    int n;
    scanf("%d", &n);
    if (n == 1)
        printf("9");
    else if (n == 2)
        printf("17");
    else if (n >= 3){
        for (int k = 3; k <= n; k++){
            next_arr(digits, temp);
            if (k % 2 == 1){
                    digits[0] += temp_odd;
                    temp_odd = digits[0];
            }
            else if (k % 2 == 0){
                    digits[0] += temp_even;
                    temp_even = digits[0];
            }
            temp = calloc(9, sizeof(long long int));
        }
        printf("%lld", sum(digits)% MOD);
    }
    return 0;
}

djm03178 5년 전 0

코드의 동작을 분석은 못 하겠지만, 모듈로는 오버플로우만 발생하지 않는다면 계속 미뤄도 됩니다. temp_odd와 temp_even에 long long의 범위를 넘어가려는 연산이 수행되지만 않았다면 상관 없습니다.

kcarollee 5년 전 0

그렇군요! 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린거 같은데 왜 맞죠?

kcarollee 5년 전 0

djm03178 5년 전 0

kcarollee 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말