|
|
| 6번째 줄: |
6번째 줄: |
|
| |
|
|
| |
|
| == '''[https://codersit.co.kr/oj/problems/1880 1. 등교 (초1)]''' == | | == '''[https://codersit.co.kr/oj/problems/1501 1. 크림빵 (초1)]''' == |
| 제목 링크를 통해 문제를 확인해주세요. | | 제목 링크를 통해 문제를 확인해주세요. |
|
| |
|
| === 📄 문제 개요 ===
| |
| 매일 아침 학교에 가는 상황을 컴퓨터 프로그램으로 해결해 보는 문제입니다.
| |
|
| |
|
| 정올이에게는 여러 대의 '''버스 시간표'''와 학교에 늦지 않게 도착해야 하는 '''기준 시간(X)'''이 주어집니다.
| |
|
| |
|
| | | == '''[https://codersit.co.kr/oj/problems/1500 2. 대피소 (초2/고1)]''' == |
| | |
| 목표는 다음 두 가지입니다.
| |
| | |
| 1. 버스를 타고 학교에 도착하는 시간이 '''기준 시간'''을 넘기지 않아야 합니다.
| |
| | |
| 2. 조건을 만족하는 버스 중 '''가장 늦게 출발하는 버스'''를 선택해야 합니다.
| |
| | |
| 만약 어떤 버스를 타도 지각한다면 '''-1을 출력'''합니다.
| |
| | |
| | |
| === 💡 문제 풀이 시뮬레이션 ===
| |
| 코드를 작성하기 전에, 먼저 주어진 상황을 분석해 봅니다.
| |
| | |
| 예를 들어 '''30분''' 안에는 학교에 도착해야 한다고 가정해 보겠습니다.
| |
| {| class="wikitable" style="text-align: center;"
| |
| | colspan="1" rowspan="1" |'''버스 번호'''
| |
| | colspan="1" rowspan="1" |출발 시간
| |
| | colspan="1" rowspan="1" |'''이동 시간'''
| |
| | colspan="1" rowspan="1" |'''🏫 학교 도착 시간'''
| |
| |-
| |
| | colspan="1" rowspan="1" |1번
| |
| | colspan="1" rowspan="1" |10분
| |
| | colspan="1" rowspan="1" |15분
| |
| | colspan="1" rowspan="1" |10 + 15 = 25분
| |
| |-
| |
| | colspan="1" rowspan="1" |2번
| |
| | colspan="1" rowspan="1" |15분
| |
| | colspan="1" rowspan="1" |20분
| |
| | colspan="1" rowspan="1" |15 + 20 = 35분
| |
| |-
| |
| | colspan="1" rowspan="1" |3번
| |
| | colspan="1" rowspan="1" |20분
| |
| | colspan="1" rowspan="1" |10분
| |
| | colspan="1" rowspan="1" |20 + 10 = 30분
| |
| |}
| |
| 과정을 차례대로 살펴보면 다음과 같습니다.
| |
| | |
| 1. 각 버스의 도착 시간(출발 시간 + 이동 시간)을 계산합니다.
| |
| | |
| 2. 도착 시간이 30분을 초과하는 2번 버스는 선택지에서 제외합니다.
| |
| | |
| 3. 남은 1번, 3번 버스 중 '''가장 늦게 출발'''하는 3번 버스(20분 출발)가 최적의 선택이 됩니다.
| |
| | |
| | |
| 복잡한 수학 공식 없이, 도착 시간을 계산하여 지각 여부를 판별하고 통과한 것 중 가장 큰 값을 고르면 됩니다.
| |
| | |
| | |
| === 💻 코드 구현 - 하나씩 모두 비교하기 ===
| |
| <syntaxhighlight lang="python3" line="1">
| |
| n, x = map(int, input().split())
| |
| | |
| ans = -1 # 초기값을 -1로 설정하여 무조건 지각하는 경우를 고려
| |
| for i in range(n):
| |
| s, t = map(int, input().split())
| |
| if s + t <= x: # 지각하지 않을 수 있다면
| |
| if ans < s: # 가장 늦게 오는 버스 시간 업데이트
| |
| ans = s
| |
| | |
| print(ans)
| |
| </syntaxhighlight>
| |
| | |
| | |
| === 📊 정답률 ===
| |
| [[파일:2024KOI등교1.png|center|class=coders70]]
| |
| | |
| | |
| == '''[https://codersit.co.kr/oj/problems/1881 2. 두 배 (초2/중1)]''' == | |
| 제목 링크를 통해 문제를 확인해주세요. | | 제목 링크를 통해 문제를 확인해주세요. |
|
| |
|
| === 📄 문제 개요 ===
| |
| 수열을 오름차순(점점 커지거나 같은 상태)으로 만들기 위해, 숫자에 '''2를 곱하는 연산'''을 최소 몇 번 해야 하는지 구하는 문제입니다.
| |
|
| |
| * '''상황:''' 앞의 숫자보다 뒤의 숫자가 작다면, 뒤의 숫자에 2를 계속 곱해서 앞의 숫자보다 크거나 같게 만들어야 합니다.
| |
| * '''목표:''' 배열 전체를 오름차순으로 만드는 데 필요한 전체 곱셈 연산의 최소 횟수를 구해야 합니다.
| |
|
| |
| '''※ 이번 문제는 log 개념을 알고 있다면 더 수월하지만, 초/중등 부문 문제인 만큼 log 사용은 배제합니다.'''
| |
|
| |
|
| |
|
| |
| === 💡 첫 번째 접근 - 직접 2를 곱해보기 ===
| |
| 가장 먼저 떠오르는 방법은 문제의 조건 그대로 앞의 숫자보다 뒤의 숫자가 작을 때마다 직접 2를 곱해보며 횟수를 세는 것입니다.
| |
|
| |
| [[파일:2024KOI두배1.png|center|class=coders100]]
| |
|
| |
| * 두 번째 숫자 1은 앞의 3보다 작기 때문에 더 커지기 위해 2를 '''2번''' 곱합니다. '''(현재 누적 연산 2회)'''
| |
| * 세 번째 숫자 5는 앞의 4보다 크기 때문에 연산을 하지 않습니다. '''(현재 누적 연산 2회)'''
| |
| * 네 번째 숫자 1은 앞의 5보다 작기 때문에 더 커지기 위해 2를 '''3번''' 곱합니다. '''(현재 누적 연산 5회)'''
| |
| * 다섯 번째 숫자 5는 앞의 8보다 작기 때문에 더 커지기 위해 2를 '''1번''' 곱합니다. '''(현재 누적 연산 6회)'''
| |
|
| |
|
| |
| === 💻 코드 구현 - 직접 2를 곱해보기 ===
| |
| <syntaxhighlight lang="python3" line="1">
| |
| n = int(input())
| |
| arr = list(map(int, input().split()))
| |
|
| |
| ans = 0
| |
|
| |
| for i in range(1, n):
| |
| while arr[i-1] > arr[i]: # 내 앞 숫자보다 커질 때까지 2를 곱하기
| |
| arr[i] *= 2
| |
| ans += 1
| |
|
| |
| print(ans)
| |
| </syntaxhighlight>이 코드로도 주어진 예제들에 대한 정답은 잘 출력되는 것을 볼 수 있습니다.
| |
| 하지만 수열의 길이(N)가 최대 250,000개일 때, '''숫자가 계속 작아지는 최악의 경우'''를 상상해 봅시다.
| |
|
| |
| 마지막 숫자는 2를 수십만 번 곱해야 하고, 숫자의 길이는 수만 자리를 넘어가게 됩니다.
| |
|
| |
| 이처럼 거대한 숫자를 매번 비교하고 곱하는 과정에서 엄청난 연산 시간이 소모되어 결국 '''시간 초과'''가 발생합니다.
| |
|
| |
| 그래서 위 코드로는 '''33점''' 획득이 가능합니다.
| |
|
| |
|
| |
| === 💡 두 번째 접근 - 곱한 횟수 기록하기 ===
| |
| 이번에는 숫자를 직접 부풀리는 대신, 이 숫자는 2를 몇 번 곱한 상태인지 '''횟수'''를 따로 기록해 두는 방법입니다.
| |
|
| |
| 현재 숫자와 이전 숫자의 '''원래 크기'''를 비교하여 다음과 같이 횟수(cnt)를 정합니다.
| |
|
| |
| * '''이전 숫자가 더 클 때 (따라잡아야 할 때)'''
| |
|
| |
| <nowiki>:</nowiki> 현재 숫자에 2를 몇 번 곱해야 이전 숫자 이상이 되는지 계산하여, 그 횟수만큼 이전 숫자의 누적 횟수에 더해줍니다.
| |
|
| |
| * '''현재 숫자가 더 클 때 (여유가 있을 때)'''
| |
|
| |
| <nowiki>:</nowiki> 현재 숫자가 이미 크기 때문에, 이전 숫자의 누적 횟수에서 2를 나눌 수 있는 만큼(여유분) 횟수를 차감해 줍니다.
| |
|
| |
| [[파일:2024KOI두배2.png|center|class=coders100]]
| |
|
| |
|
| |
| === 💻 코드 구현 - 곱한 횟수 기록하기 ===
| |
| <syntaxhighlight lang="python3" line="1">
| |
| import sys
| |
| input = sys.stdin.readline
| |
|
| |
| n = int(input())
| |
| a = list(map(int, input().split()))
| |
|
| |
| ans = 0
| |
| cnt = 0
| |
|
| |
| for i in range(1, n):
| |
| prev, curr = a[i-1], a[i]
| |
|
| |
| if prev > curr: # 이전 숫자가 더 크다면
| |
| k = 0
| |
| tmp = curr
| |
| while tmp < prev: # 2를 곱하는 횟수 누적
| |
| tmp *= 2
| |
| k += 1
| |
| cnt += k
| |
|
| |
| else: # 현재 숫자가 더 크다면
| |
| k = 0
| |
| tmp = prev
| |
| while tmp * 2 <= curr: # 여유 횟수만큼 누적
| |
| tmp *= 2
| |
| k += 1
| |
| cnt = max(0, cnt - k) # 이전 누적 횟수에서 여유분 차감(cnt - k), 0보다 작아질 수는 없음
| |
|
| |
| ans += cnt
| |
|
| |
| print(ans)
| |
| </syntaxhighlight>숫자를 직접 곱하지 않고 원래 숫자들 간의 '''스케일 차이만 비교'''하기 때문에 20만 개의 숫자가 주어져도 무리없이 '''100점을''' 받을 수 있습니다.
| |
|
| |
|
| |
| === 📊 정답률 ===
| |
| [[파일:2024KOI두배3.png|center|class=coders70]]
| |
|
| |
| [[파일:2024KOI두배4.png|center|class=coders70]]
| |
|
| |
|
| === '''''' ===
| |
|
| |
|
| == '''[https://codersit.co.kr/oj/problems/1882 3. 반품 회수 (초3/고1)]''' == | | == '''3. 아이템 획득 (초3)''' == |
| 추가 예정 | | 추가 예정 |
