2024 한국정보올림피아드(KOI) 1차 대회 2교시 초등부: 두 판 사이의 차이

아두위키 : Arduwiki
시각위키텍스트
잔글편집 요약 없음
9번째 줄: 9번째 줄:
제목 링크를 통해 문제를 확인해주세요.
제목 링크를 통해 문제를 확인해주세요.


=== '''📄 문제 개요''' ===
=== 📄 문제 개요 ===
1부터 N까지의 숫자가 각각 두 번씩 적힌 2N장의 카드가 일렬로 주어졌을 때,
매일 아침 학교에 가는 상황을 컴퓨터 프로그램으로 해결해 보는 문제입니다.


① 같은 숫자가 적힌 두 카드를 한 쌍으로 짝지어
정올이에게는 여러 대의 '''버스 시간표'''와 학교에 늦지 않게 도착해야 하는 '''기준 시간(X)'''이 주어집니다.


② 두 카드 사이에 놓인 다른 카드의 개수를 계산하고


그 중 '''두 카드 사이에 있는 카드 개수의 최댓값'''을 구하는 문제입니다.


[[파일:2025KOI먼카드1.png|center|class=coders70]]
목표는 다음 두 가지입니다.


'''문제에 적힌 내용을 조금 더 정확하게 이해해봅시다.'''
1. 버스를 타고 학교에 도착하는 시간이 '''기준 시간'''을 넘기지 않아야 합니다.


* 1이 적힌 두 카드 사이에는 차례로 2, 2, 4, 3이 적힌 카드가 있으므로, "1 사이 카드 수"는 4이다.
2. 조건을 만족하는 버스 중 '''가장 늦게 출발하는 버스'''를 선택해야 합니다.
* 2가 적힌 두 카드 사이에는 아무 카드도 없으므로, "2 사이 카드 수"는 0이다.
* 3이 적힌 두 카드 사이에는 1이 적힌 카드만 있으므로, "3 사이 카드 수"는 1이다.  
* 4가 적힌 두 카드 사이에는 차례로 3, 1, 3이 적힌 카드가 있으므로, "4 사이 카드 수"는 3이다.  


만약 어떤 버스를 타도 지각한다면 '''-1을 출력'''합니다.


위 그림을 보면 1과 1 사이 카드가 4장있는 경우가 가장 카드가 많은 경우이므로 정답은 4가 됩니다.
=== 💡 문제 풀이 시뮬레이션 ===
코드를 작성하기 전에, 먼저 주어진 상황을 분석해 봅니다.


예를 들어 '''30분''' 안에는 학교에 도착해야 한다고 가정해 보겠습니다.
{| class="wikitable sortable"
| 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. 각 버스의 도착 시간(출발 시간 + 이동 시간)을 계산합니다.
가장 쉽게 먼저 떠오르는 방법은 카드를 하나 잡고 뒤에 있는 카드들을 일일이 뒤집어보며 똑같은 숫자를 찾는 것입니다.


[[파일:2025KOI먼카드2.png|center|class=coders100]]
2. 도착 시간이 30분을 초과하는 2번 버스는 선택지에서 제외합니다.


그림을 보면 처음 숫자 1의 '''위치(인덱스)는 0''', 이후 뒤를 찾아보면 '''5번 위치(인덱스)'''에 1이 한 번 더 있는 것을 확인할 수 있습니다.
3. 남은 1번, 3번 버스 중 '''가장 늦게 출발'''하는 3번 버스(20분 출발)가 최적의 선택이 됩니다.


뒤에 숫자 위치(5)에서 처음 숫자 위치(0)을 빼고, 양 끝 숫자가 모두 포함이 안 되기 때문에 1을 한 번 더 빼면 카드의 개수가 나옵니다.


위와 같은 방법으로 코드를 짜보면 다음과 같습니다.
복잡한 수학 공식 없이, 도착 시간을 계산하여 지각 여부를 판별하고 통과한 것 중 가장 큰 값을 고르면 됩니다.
 


=== 💻 '''코드 구현 - 하나씩 모두 비교하기''' ===
=== 💻 '''코드 구현 - 하나씩 모두 비교하기''' ===
<syntaxhighlight lang="python3" line="1">
<syntaxhighlight lang="python3" line="1">
n = int(input())
n, x = map(int, input().split())
arr = list(map(int, input().split()))


ans = 0
ans = -1 # 초기값을 -1로 설정하여 무조건 지각하는 경우를 고려
for i in range(2*n): # 카드 전체 돌아보기
for i in range(n):
     for j in range(i+1, 2*n): # 현재 위치보다 뒤를 확인
     s, t = map(int, input().split())
         if arr[i] == arr[j]: # 같은 숫자를 찾은 경우
    if s + t <= x: # 지각하지 않을 수 있다면
             ans = max(ans, j-i-1) # 숫자 사이 카드 개수의 최대값 계산
         if ans < s: # 가장 늦게 오는 버스 시간 업데이트
            break
             ans = s


print(ans)
print(ans)
</syntaxhighlight>이번 문제는 1번 문제인 만큼 N의 최대 크기가 작기 때문에'''(1 <= N <= 2000)''' 이렇게 중첩반복의 형태로 풀어도 100점을 받을 수 있습니다.
</syntaxhighlight>
 
하지만 여기에서 N의 범위가 조금만 넓어지게 되면 지금처럼 '''시간복잡도 O(N^2)'''의 방법으로는 '''시간초과'''가 나올 수 있습니다.
 
따라서 정보올림피아드에 도전하는 학생들이라면 조금 더 좋은 방법을 생각해볼 필요가 있습니다.
 
 
=== '''💡 두 번째 접근 - 카드 번호 처음 등장 위치 메모해두기''' ===
이번에는 카드를 왔다갔다 여러 번 뒤집지 않고, 카드 번호마다 처음 등장한 위치를 메모해두는 방법입니다.
 
[[파일:2025KOI먼카드3.png|center|class=coders100]]
 
해당 카드 숫자를 처음 찾았을 때 '''위치를 메모'''해두고, 이후에 그 숫자를 다시 찾았을 때는
 
메모를 보고 숫자 사이에 카드가 몇 개 있었는지 바로 확인할 수 있습니다.
 
'''숫자 사이의 카드 개수 = 다시 찾았을 때 위치 - 메모에 기록된 처음 위치 - 1'''
 
=== 💻 '''코드 구현 - 카드 번호 처음 등장 위치 메모해두기''' ===
<syntaxhighlight lang="python3" line="1">
n = int(input())
 
arr = list(map(int, input().split()))
memo = [-1] * (n+1) # 카드 번호 처음 위치 메모
ans = 0
 
for i in range(2*n):
    if memo[arr[i]] == -1: # -1: 처음 찾은 숫자
        memo[arr[i]] = i # 처음 찾은 숫자의 위치 메모
    else: # 이미 찾았던 숫자
        ans = max(ans, i - memo[arr[i]] - 1) # 두 위치 사이 카드 개수의 최대값 계산
       
print(ans)
</syntaxhighlight>카드 개수는 N개이지만 메모 칸 수를 N+1로 설정했습니다.
 
원래는 없는 가상의 0번 카드 자리를 만들어 실제 숫자와 인덱스를 똑같이 맞춰주었습니다.
 
이 방법으로 문제를 풀게 되면 '''시간 복잡도는 O(N)'''으로 카드 리스트를 한 바퀴만 돌아도 답을 바로 구해낼 수 있게 됩니다.
 
 
실제로 두 방법으로 코드를 제출해보면 어마어마한 시간 차이를 확인할 수 있습니다.
 
[[파일:2025KOI먼카드4.png|center|class=coders70]]


아래 : 첫 번째 접근 방식 / 위 : 두 번째 접근 방식


=== 📊 '''정답률''' ===
=== 📊 '''정답률''' ===
[[파일:2025KOI먼카드5.png|center|class=coders70]]
[[파일:2024KOI등교1.png]]


== '''[https://codersit.co.kr/oj/problems/1881 2. 두 배 (초2/중1)]''' ==
== '''[https://codersit.co.kr/oj/problems/1881 2. 두 배 (초2/중1)]''' ==

2026년 4월 13일 (월) 19:36 판


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

한국정보올림피아드(KOI) 기출 문제 풀이 모음
한국정보올림피아드(KOI) 기출 문제 풀이 모음


1. 등교 (초1)

제목 링크를 통해 문제를 확인해주세요.

📄 문제 개요

매일 아침 학교에 가는 상황을 컴퓨터 프로그램으로 해결해 보는 문제입니다.

정올이에게는 여러 대의 버스 시간표와 학교에 늦지 않게 도착해야 하는 기준 시간(X)이 주어집니다.


목표는 다음 두 가지입니다.

1. 버스를 타고 학교에 도착하는 시간이 기준 시간을 넘기지 않아야 합니다.

2. 조건을 만족하는 버스 중 가장 늦게 출발하는 버스를 선택해야 합니다.

만약 어떤 버스를 타도 지각한다면 -1을 출력합니다.

💡 문제 풀이 시뮬레이션

코드를 작성하기 전에, 먼저 주어진 상황을 분석해 봅니다.

예를 들어 30분 안에는 학교에 도착해야 한다고 가정해 보겠습니다.

버스 번호 출발 시간 이동 시간 🏫 학교 도착 시간
1번 10분 15분 10 + 15 = 25분
2번 15분 20분 15 + 20 = 35분
3번 20분 10분 20 + 10 = 30분

과정을 차례대로 살펴보면 다음과 같습니다.

1. 각 버스의 도착 시간(출발 시간 + 이동 시간)을 계산합니다.

2. 도착 시간이 30분을 초과하는 2번 버스는 선택지에서 제외합니다.

3. 남은 1번, 3번 버스 중 가장 늦게 출발하는 3번 버스(20분 출발)가 최적의 선택이 됩니다.


복잡한 수학 공식 없이, 도착 시간을 계산하여 지각 여부를 판별하고 통과한 것 중 가장 큰 값을 고르면 됩니다.


💻 코드 구현 - 하나씩 모두 비교하기

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)


📊 정답률

2. 두 배 (초2/중1)

제목 링크를 통해 문제를 확인해주세요. 추가 예정

3. 반품 회수 (초3/고1)

추가 예정

원본 주소 "https://arduwiki.com/html/index.php?title=2024_한국정보올림피아드(KOI)_1차_대회_2교시_초등부&oldid=2817"