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

 

오늘의 문제

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

 

드디어 실버 1 문제!

정답 비율이 33% 인 것을 보니 또 생각이 좀 필요하겠군.

 

권장시간 안에 푸는건 글렀다.    라고 생각했다. ㅋㅋㅋㅋㅋ

역시나, 1시간 30분 권장 시간을 넘겨 2시간 40분 정도 걸렸다. ㅎ....그래도 푼게 어디냐!!! 🤭🔥

---

나의 첫 번째 풀이 (성공)

솔직히 말하면 오늘은 문제를 보고 ???? 하다가 이진탐색인가?싶었다.

대충 문제는 이해가 가는데, 강의를 나누는 갯수를 어떤식으로 표현해야할지가 감이 안 왔다.

 

대충 막대기를 끼워넣는다고 생각하면서 인덱스를 사용해야 하나?

근데 또 강의 시간의 합을 비교해야 하는 건데, 코드가 복잡해진다는 생각도 들고....

 

그래서 일단은 파이참에 이분탐색 기본 코드 틀을 입력했다.

저번에 배운대로 입력은 sys.stdin.readline을 사용 😸

 

그 상태로 강의의 합을 어떻게 나누는게 좋을까 고민했다.

고민하는 시간으로 2시간 보낸 것 같다 ㅋㅋㅋㅋㅋ (짜증내는 시간 10분...)

 

그러다 불현듯 mid 값 기준으로 합을 비교하고 그 부분을 초기화시키고 초기화시킨 횟수

즉, 강의 사이에 끼워넣을 막대기 수를 세면 되겠다는 생각이 들었다. 

 

그렇게 코드를 작성. 

 

import sys

n, m = map(int, sys.stdin.readline().split())
lectures = list(map(int, sys.stdin.readline().split()))

result = 0
start = max(lectures)
end = sum(lectures)

while start <= end:
    mid = (start+end)//2
    total = 0
    count = 1
    for lecture in lectures:
        if total+lecture > mid:
            total = 0
            count += 1
        total += lecture

    if count <= m:
        result = mid
        end = mid-1
    else:
        start = mid+1

print(result)

 

 

행복하게 통과 받을 수 있었다. ❤️

그리고 오늘 이진탐색에 대해서 뭔가를 깨달을 수 있었다.

 

---

 

 

이진탐색(이분탐색) 문제 솔루션

** 기본적인 이진탐색 함수 내용 파악하기

 

** 길이, 위치, 합 등의 문제 유형이 있음

 

** 문제에서 출력해야하는 값 즉, 찾고 있는 값을 target으로 생각

👉 위의 문제 유형을 파악해서 그에 맞도록 잘 설정해야함

 

** mid 를 좁혀가면서, mid를 통해 target을 찾는다고 생각하자

 

** 중요한건 언제나 mid!!!!

 

 

---

오늘 한 공부

1. 토익 보카 day6 암기

2. 코테 1문제 - 깃헙 업로드

3. 대규모 시스템 설계 기초 2장 조금 읽기

4. TIL 적기

+++ 낮잠😂

 

컨디션 이슈로 쉬엄쉬엄 하고 있다 🥲

건강 챙기자..