글 읽기 - 정답인데 왜 정답인지 모르겠습니다.

yordlejason 6년 전 0

틀린 정답을 제출했을 때에는 15번줄, 즉 일반적인 케이스에서 %1000000000을 해주지 않았습니다.

정답 처리를 받았을 때에는 15번줄에서 %1000000000을 추가해줬구요 (이 부분은 저와 같은 이유로 틀리신 분들이 이렇게 하고 정답처리를 받았다 하기에 추가해봤습니다.)

왜 일반적인 케이스를 처리하면서 %1000000000을 해줘야 하는지 이해가 잘 안가네요.

문제상에서는

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

라고 되어있는데요..

다른분들이 질문하신것 읽어봤는데 잘 이해가 안가 질문 올립니다.

송구스럽지만 가능하시다면 구체적인 예시와 설명 부탁드립니다.

감사합니다 :-)

def total_cases(n):
    D = [[0 for row in range(10)] for col in range(n+1)] # D[i][j] 형식의 2차원 배열 생성

    # 예외 2: 가정이 거짓
    for j in range(1, 10):
        D[1][j] = 1

    for i in range(2, n+1):
        for j in range(10):
            if j == 0:  # 예외 1-1: 마지막 자리가 0
                D[i][0] = D[i-1][1]
            elif j == 9: # 예외 1-2: 마지막 자리가 9
                D[i][9] = D[i-1][8]
            else: # 일반적인 케이스
                D[i][j] = (D[i-1][j-1] + D[i-1][j+1])%1000000000

    return sum(D[n])
print(total_cases(int(input()))%1000000000)

seni 6년 전 3

해당 언어는 잘 모르겠으나 c/c++ 기준에서 말씀드리면..

정답을 sum에 더해갈 때 overflow가 발생하는데 이때 정답과는 완전히 다른 숫자가 되버리므로 틀리게 됩니다. 따라서 10억의 나머지 연산을 계속 해준 것으로 정답을 제출하는데.. 문제 요구사항도 그렇고요

그런데 정답을 계산할 때 뿐만 아니라 일반 케이스에서도 더하다보면 수십억을 쉽게 넘어가게 됩니다. 따라서 일반 케이스에서도 나머지 연산을 해줍니다.

limjihun204 5년 전 1

원래 마지막 답 낼때 나눠줘도 되지만 그렇게 할경우 int가 가질 수 있는 범위를 넘어서게 되면서 오버플로우가 발생해서 답이 틀려지는 걸로 생각합니다.

그래서 오버플로우가 발생하기 않도록 매 케이스마다 나눠주는 거죠

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

문제

문제

출처

ICPC

정답인데 왜 정답인지 모르겠습니다.

yordlejason 6년 전 0

seni 6년 전 3

limjihun204 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말