ArduWiki: /* 2. 회의 장소 (중2) */

2026-04-13T13:37:42Z

2. 회의 장소 (중2)

← 이전 판		2026년 4월 13일 (월) 22:37 판
111번째 줄:		111번째 줄:


	== '''~~[https://codersit.co.kr/oj/problems/1882~~ 2. 회의 장소 (중2)]''' ==		== '''2. 회의 장소 (중2)''' ==
	추가 예정		추가 예정


	== '''~~[https://codersit.co.kr/oj/problems/1882~~ 3. 이진 트리 (중3/고2)]''' ==		== '''3. 이진 트리 (중3/고2)''' ==
	추가 예정		추가 예정

ArduWiki: 새 문서: {{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2024 KOI, 2024 중등부 1차 대회 2교시|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.|image=https://arduwiki.com/html/resources/assets/ard...

2026-04-13T13:37:25Z

새 문서: {{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2024 KOI, 2024 중등부 1차 대회 2교시|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.|image=https://arduwiki.com/html/resources/assets/ard...

새 문서

{{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2024 KOI, 2024 중등부 1차 대회 2교시|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.|image=https://arduwiki.com/html/resources/assets/arduwiki.png}}

'''한국 정보올림피아드(KOI) 기출 문제 풀이과정을 수록합니다.'''

[[파일:KOISolution.jpg|link=https://arduwiki.com/wiki/%ED%95%9C%EA%B5%AD%EC%A0%95%EB%B3%B4%EC%98%AC%EB%A6%BC%ED%94%BC%EC%95%84%EB%93%9C(KOI)|한국정보올림피아드(KOI) 기출 문제 풀이 모음|center|class=coders100]]

== '''[https://codersit.co.kr/oj/problems/1881 1. 두 배 (초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 2. 회의 장소 (중2)]''' ==
추가 예정

== '''[https://codersit.co.kr/oj/problems/1882 3. 이진 트리 (중3/고2)]''' ==
추가 예정

2024 한국정보올림피아드(KOI) 1차 대회 2교시 중등부 - 편집 역사

ArduWiki: /* 2. 회의 장소 (중2) */