기억 ( 누적합 ) #2304 문제 고민

감사합니다 선생님.. 저도 문과 출신에 늦은 나이에 코딩에 입문을 했는데

선생님의 말씀에 힘을 내봅니닷!!! 허허허헣

그래서 한참을 뚫어져라 문제를 보다가 나름 저만의 방식? 으로 문제를 풀어 보았는데요

출력은 잘 되는데 백준에 제출을 하려니 95프로에서 틀렸습니다가 나오네요 ㅜㅜ

아래는 코드 내용입니다. 주석을 열심히 달아보았어용..

경우의 수를 많이 입력 해봤는데 반례를 찾지 못해서 이렇게 여쭙습니다 흙..

A = int(input())

arr = []

for i in range(A):
    arr.append(list(map(int,input().split())))

#기둥 위치별로 정렬 위치, 높이
arr.sort()

# 가장 높은 기둥 하나의 위치만 구하기
high_arr = []

for j in range(A):
    high_arr.append(arr[j][1])

max_high_idx = high_arr.index(max(high_arr))

#앞 부분 부터 가장 높은 기둥 까지의 합 변수 선언
front_answer = 0
#뒷 부분 부터 가장 높은 기둥 까지의 합 변수 선언 (여기서 가장 높은 기둥의 면적을 포함 시킬 것)
back_answer = 0

#다음 기둥의 위치 - 현재기둥의 위치 * 기둥의 높이 방식으로 계산을 할 것이기 때문에
#기준이 되는 기둥의 위치를 유연하게 조정하기 위해 변수 선언
front_std_pillar = 0
back_std_pillar = A-1

for i in range(1, A):

    #기준이 되는 기둥의 인덱스가 max_high_idx와 일치할 때 break
    if arr.index(arr[front_std_pillar]) == max_high_idx:
        break

    #기준이 되는 기둥보다 다음에 오는 기둥이 높을 경우 거리만큼 면적을 곱해준다.    
    if arr[i][1] >= arr[front_std_pillar][1]: #다음 기둥의 높이 >= 현재 기둥의 높이 일때
        front_answer += (arr[front_std_pillar][1])*(arr[i][0] - arr[front_std_pillar][0])  #기둥 * 다음 기둥의 위치 - 현재기둥의 위치)
        front_std_pillar = i #계산이 이루어졌을 때는 기준 기둥의 위치를 i로 업데이트 
        continue

    #다음 기둥이 낮을 경우에는 pass해도 된다 -> i가 자동으로 1씩 추가 되기 때문에 pass 가능

for j in range(A-2, -1, -1):

    if arr[j][1] >= arr[back_std_pillar][1]: #다음 기둥의 높이 >= 현재 기둥의 높이 일때
        back_answer += (arr[back_std_pillar][1])*(arr[back_std_pillar][0] - arr[j][0])  #기둥 * 다음 기둥의 위치 - 현재기둥의 위치)
        back_std_pillar = j #다음 단계로 가기.
    
    if arr.index(arr[back_std_pillar]) == max_high_idx:
        back_answer += arr[back_std_pillar][1]
        break
print(back_answer + front_answer)

반례입니다!
1
1 1

질문자님 코드에서는 0이라고 나오는데 정답은 1이죠?

100%에 가까워져서 틀리는 경우는 반례를 놓치고 계실 경우가 많습니다!

위 반례 해결하고 다시 제출해봐주세요!

감사합니다! 선생님!

제가 기둥이 하나만 주어졌을 때의 경우의 수를 생각하지 못했네요...

간단하게

if A == 1:
    back_answer = arr[0][1]

이걸 추가해서 해결했습니다! 드디어 통과 되었네요 ㅠㅜ 감사합니다!

여쭙고 싶은게 있는데

어떻게 반례를 찾으신거죠...?

반례를 찾는 통찰력을 어떻게 하면 가질수 있는지 궁금합니다 ㅜㅜ

저도 풀어본 문제고 저도 똑같이 반례를 못찾아 본 적이 있어서, 틀려본 적이 있어서 찾을 수 있는것 같습니다!

질문자님도 이제 똑같은 문제에 95%에서 틀리는 분을 보시면 이번 반례가 떠오르실겁니다 🙂 !! 성공하신거 축하드려요!! 😄

그 외에도,

보통 반례가 경계선이라고해서

0에 가까운 친구 ( 변수가 1이거나 0인 친구 )

한계값에 가까운 친구 ( max값에 가깝거나 max값보다 하나 작은 친구 )

에서 많이 나옵니다!

이건 경험하다보면 익숙해지실거에요 :)!!