글 읽기 - 반례가 어떤 것이 있을까요??

sang712 1년 전 0

16507 문제를 1차원 부분합으로 풀었는데 시간이 너무 오래 걸리는 것 같아서 2차원으로 만들어서 시도를 하였습니다.

예제는 다 맞고

예제를 이용해서 여러 부분의 합을 테케로 했을 때도 다 맞는 데

제출했을 경우 틀렸다고 나옵니다.

어디서 틀렸는지 반례를 찾아주실 수 있을까요?

import sys
input = sys.stdin.readline

R, C, Q = map(int, input().split())

K = []
# 1) 구현 - 시간초과
# for _ in range(R):
#     K.append(list(map(int, input().split())))

# 2) 1차원 부분합 - 3288ms
# for _ in range(R):
#     k = list(map(int, input().split()))
#     for i in range(1, C):
#         k[i] += k[i-1]
#     K.append(k)

# 3) 2차원 부분합
for i in range(R):
    k = list(map(int, input().split()))
    for j in range(1, C):
        k[j] += k[j-1]
        if i > 0:
            k[j] += K[i-1][j] - K[i-1][j-1]
    K.append(k)

# 1) 구현    
# def brightness(r1, r2, c1, c2):
#     pixels = (r2-r1+1) * (c2-c1+1)
#     bright = 0
#     for r in range(r1-1, r2):
#         bright += sum(K[r][c1-1:c2])
#     return bright//pixels

# 2) 1차원 부분합
# def brightness(r1, r2, c1, c2):
#     pixels = (r2-r1+1) * (c2-c1+1)
#     bright = 0
#     for r in range(r1-1, r2):
#         bright += K[r][c2-1]
#         if c1 > 1: bright -= K[r][c1-2]
#     return bright//pixels

# 3) 2차원 부분합
def brightness(r1, r2, c1, c2):
    pixels = (r2-r1+1) * (c2-c1+1)
    bright = K[r2-1][c2-1]
    if r1 > 1:
        bright -= K[r1-2][c2-1]
    if c1 > 1:
        bright -= K[r2-1][c1-2]
    if r1 > 1 and c1 > 1:
        bright += K[r1-2][c1-2]
    return bright//pixels

for _ in range(Q):
    r1, c1, r2, c2 = map(int, input().split())
    print(brightness(r1, r2, c1, c2))

jbkmath48128 1년 전 1

input:
5 6 1
4 1 3 4 9 5
1 2 8 7 5 5
8 1 2 5 3 2
1 5 3 4 2 5
5 2 1 2 3 5
1 1 5 1

answer: 3 (19//5)
output: 1

1열의 경우 배열 K에 저장되는 값이 실제와 다른 것 같습니다.

sang712 1년 전 0

해결했습니다 감사합니다~!😁👍

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

문제

문제

출처

ICPC

반례가 어떤 것이 있을까요??

sang712 1년 전 0

jbkmath48128 1년 전 1

sang712 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말