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

2024-03-22T01:33:57.565Z

0

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

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

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

출력은 잘 되는데 백준에 제출을 하려니 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)

0

반례입니다!
1
1 1

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

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

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

0

감사합니다! 선생님!

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

간단하게

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

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

여쭙고 싶은게 있는데

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

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

0

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

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

그 외에도,

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

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

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

에서 많이 나옵니다!

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