[IT/코딩테스트] 99클럽 코테 스터디2일차 TIL + BOJ1654

 

오늘의 문제

https://www.acmicpc.net/problem/1654

문제

 

문제를 보자마자 든 생각은.

이번에는 왜 때문에 실버2가 정답률이 21.682% 일까..... 였다

 

어제는 시간 초과를 노린 문제였다면 과연 오늘은 뭘까!

 

그리고 역시 기대를 저버리지 않고 나 또한 그 함정에 걸려드는데.....

 

---

나의 첫 번째 풀이 (실패)

사실. 오늘은 문제를 보고 이거 어디서 많이 봤는데??? 싶었다 ㅋㅋㅋ

어제 문제 오답하면서 이진탐색(이분탐색) 강의를 들었는데, 오예~ 누가봐도 그 문제(가래떡 문제)랑 너무 유사했다.

** 핵심 
1) 시작점, 끝점
2) 중간점 만들기
3) 기준 이하 : 끝점을 중간점-1 로 만들기
4) 기준 이상 : 시작점을 중간점+1 로 만들기

 

그래서 어제 배운 내용 생각하면서 열심히 코드를 적었다.

 

당연히 맞을 줄 알고 싱글벙글 하고 있었다.

백준에 넣었던 코드는 아래와 같다.

array = []
k, n = map(int, input().split())

for _ in range(k):
    array.append(int(input()))

# 시작점, 끝점
start = 0
end = max(array)

# 이진 탐색 수행
result = 0
while(start <= end):
    total = 0
    mid = (start + end)//2
    for i in array:
        total += (i//mid)
    # 덜 만들어진 경우
    if total < n:
        end = mid - 1
    # 같거나 더 만들어진 경우
    else:
        result = mid
        start = mid + 1

print(result)

 

런타임에러가되...

 

그런데 생각지도 못한 에러가....?

냅다 런타임 에러(ZeroDivisionError)가 떴다.

 

사실 틀렸으면 틀렸지 런타임 에러는 뭐지? 싶어서 바로 검색을 했고

백준 사이트에 누가 런타임 에러에 대해서 질문한 것을 확인할 수 있었다.

 

그리고 8가지로 어떤 친절한 분이 정리해주셨다.

 

** 링크

https://www.acmicpc.net/board/view/22980

런타임에러가 나는 경우

 

 

오답 원인 파악 하기

그렇다면, ZeroDivisionError 은 왜 발생한 걸까....

 

문제 발생 지점을 찾기 위해서 변수로 나누는 부분을 찾아보았고

갑자기 어제 정리한 SPOF 생각남

 

mid = (start + end)//2
for i in array:
    total += (i//mid)

 

위의 부분이 눈에 띄었다.

mid 가 0이 된다면 오류가 발생할 수도 있는 부분.

그렇다면 mid 가 0이 되는 상황을 방지해주어야 하는데, 그러려면 start 가 0이 되어서는 안 된다.

 

end 가 0이나 1이면 start가 0일 때, mid 가 0이 된다.

 

그래서 start 값을 1로 수정했고.

맞았다.

 

뿌듯

 

 

해결 방안

수정한 코드는 아래와 같다. start 값을 1로 설정.

array = []
k, n = map(int, input().split())

for _ in range(k):
    array.append(int(input()))

# 시작점, 끝점
start = 1
end = max(array)

# 이진 탐색 수행
result = 0
while(start <= end):
    total = 0
    mid = (start + end)//2
    for i in array:
        total += (i//mid)
    # 덜 만들어진 경우
    if total < n:
        end = mid - 1
    # 같거나 더 만들어진 경우
    else:
        result = mid
        start = mid + 1

print(result)

 

 

그래도 나름 문제를 보고 '이분탐색으로 풀어야겠다' 라고 생각했던 것이 뿌듯했다🤭

오늘 이분탐색 한 번 더 복습하고 깃헙에 내용 정리 올려야겠다.

 

화이또~!

---

오늘 한 공부

1. 코테 1문제

2. 이진탐색(이분탐색) 강의 듣기

3. 강의 들은 내용 정리 - 깃헙 업로드

4. 대규모 시스템 설계 기초 : 2장 ( ~ ) 정리

5. 영어 보카 DAY5 암기

6. 정처기 필기 공부 계획 세우기

7. TIL 적기