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

2026년 5월 29일 (금) 13:56에 ArduWiki님의 편집

2026-05-29T13:56:19Z

← 이전 판		2026년 5월 29일 (금) 22:56 판
6번째 줄:		6번째 줄:


	== '''[https://~~codersit~~.~~co.kr/oj~~/problems/1369 1. 빵 (초1)]''' ==		== '''[https://coj.ac/problems/1369 1. 빵 (초1)]''' ==
	제목 링크를 통해 문제를 확인해주세요.		제목 링크를 통해 문제를 확인해주세요.

60번째 줄:		60번째 줄:


	== '''[https://~~codersit~~.~~co.kr/oj~~/problems/1464 2. 조약돌 (초2)]''' ==		== '''[https://coj.ac/problems/1464 2. 조약돌 (초2)]''' ==
	제목 링크를 통해 문제를 확인해주세요.		제목 링크를 통해 문제를 확인해주세요.

2026년 5월 8일 (금) 13:47에 ArduWiki님의 편집

2026-05-08T13:47:14Z

← 이전 판		2026년 5월 8일 (금) 22:47 판
126번째 줄:		126번째 줄:
	▶ 갱신된 DP 테이블: DP = [0, 0, 0, 0, 1]		▶ 갱신된 DP 테이블: DP = [0, 0, 0, 0, 1]

	[[파일:2022KOI조약돌5.png\|center\|class=coders100]]		[[파일:2022KOI조약돌5.png\|center\|class=coders100]]

	'''2. 0번 위치를 건너뛰고 1번 위치부터 시작'''		'''2. 0번 위치를 건너뛰고 1번 위치부터 시작'''

2026년 5월 8일 (금) 13:46에 ArduWiki님의 편집

2026-05-08T13:46:43Z

← 이전 판		2026년 5월 8일 (금) 22:46 판
125번째 줄:		125번째 줄:

	▶ 갱신된 DP 테이블: DP = [0, 0, 0, 0, 1]		▶ 갱신된 DP 테이블: DP = [0, 0, 0, 0, 1]


	[[파일:2022KOI조약돌5.png\|center\|class=coders100]]		[[파일:2022KOI조약돌5.png\|center\|class=coders100]]

2026년 5월 8일 (금) 13:46에 ArduWiki님의 편집

2026-05-08T13:46:06Z

← 이전 판		2026년 5월 8일 (금) 22:46 판
118번째 줄:		118번째 줄:
	[[파일:2022KOI조약돌4.png\|center\|class=coders100]]		[[파일:2022KOI조약돌4.png\|center\|class=coders100]]

			'''1. 0번 위치에서 제거 시작'''

	'''1. 0번 위치에서 제거 시작'''

	* 0번 위치의 돌(2개)부터 시작해 인접한 돌들을 묶어서 연쇄적으로 치워나갑니다.		* 0번 위치의 돌(2개)부터 시작해 인접한 돌들을 묶어서 연쇄적으로 치워나갑니다.

2026년 5월 8일 (금) 13:45에 ArduWiki님의 편집

2026-05-08T13:45:20Z

← 이전 판		2026년 5월 8일 (금) 22:45 판
78번째 줄:		78번째 줄:
	그렇다면 우리는 이 N번의 작업에서 횟수를 절약할 수 있는 경우를 찾아 빼줘야 합니다.		그렇다면 우리는 이 N번의 작업에서 횟수를 절약할 수 있는 경우를 찾아 빼줘야 합니다.

	~~[[파일:2022KOI조약돌1.png]]~~

			[[파일:2022KOI조약돌1.png\|center\|class=coders100]]


	우리가 이 N번의 전체 횟수를 절약할 수 있는 유일한 방법은 바로 이전 장소와 현재 장소의 돌을 짝지어 동시에 치우는 것(1번 작업)뿐입니다.		우리가 이 N번의 전체 횟수를 절약할 수 있는 유일한 방법은 바로 이전 장소와 현재 장소의 돌을 짝지어 동시에 치우는 것(1번 작업)뿐입니다.

87번째 줄:		86번째 줄:

	연쇄적으로 돌을 지워나가다가 돌이 애매하게 남아버리면, 결국 누군가가 그 자리에 가서 2번 작업을 또 써야 하기 때문입니다.		연쇄적으로 돌을 지워나가다가 돌이 애매하게 남아버리면, 결국 누군가가 그 자리에 가서 2번 작업을 또 써야 하기 때문입니다.



	[[파일:2022KOI조약돌2.png]]		[[파일:2022KOI조약돌2.png\|center\|class=coders100]]

	따라서 우리가 찾아야할 상황은 이전 위치와 엮어서 지워나가다가, '''남는 돌 없이 양쪽이 완벽하게 청소되어 횟수가 절약되는 순간'''입니다.		따라서 우리가 찾아야할 상황은 이전 위치와 엮어서 지워나가다가, '''남는 돌 없이 양쪽이 완벽하게 청소되어 횟수가 절약되는 순간'''입니다.
97번째 줄:		95번째 줄:


	[[파일:2022KOI조약돌3.png]]		[[파일:2022KOI조약돌3.png\|center\|class=coders100]]

	앞선 그림에서 보았듯, 돌을 완벽하게 치워서 횟수를 절약하려면 연쇄 작용이 딱 맞아떨어져야 합니다.		앞선 그림에서 보았듯, 돌을 완벽하게 치워서 횟수를 절약하려면 연쇄 작용이 딱 맞아떨어져야 합니다.
118번째 줄:		116번째 줄:
	* 초기 상태: DP = [0, 0, 0, 0, 0] (아직 한 번도 절약하지 못함)		* 초기 상태: DP = [0, 0, 0, 0, 0] (아직 한 번도 절약하지 못함)

	[[파일:2022KOI조약돌4.png]]		[[파일:2022KOI조약돌4.png\|center\|class=coders100]]


131번째 줄:		129번째 줄:


	[[파일:2022KOI조약돌5.png]]		[[파일:2022KOI조약돌5.png\|center\|class=coders100]]

	'''2. 0번 위치를 건너뛰고 1번 위치부터 시작'''		'''2. 0번 위치를 건너뛰고 1번 위치부터 시작'''
191번째 줄:		189번째 줄:
	print(n - dp[-1])		print(n - dp[-1])
	</syntaxhighlight>		</syntaxhighlight>

	~~=== ===~~

2026년 5월 8일 (금) 13:44에 ArduWiki님의 편집

2026-05-08T13:44:30Z

← 이전 판		2026년 5월 8일 (금) 22:44 판
62번째 줄:		62번째 줄:
	== '''[https://codersit.co.kr/oj/problems/1464 2. 조약돌 (초2)]''' ==		== '''[https://codersit.co.kr/oj/problems/1464 2. 조약돌 (초2)]''' ==
	제목 링크를 통해 문제를 확인해주세요.		제목 링크를 통해 문제를 확인해주세요.


			=== 📄 문제 개요 ===
			좌우 일렬로 놓인 N개의 장소에 조약돌이 있습니다. 다음 두 가지 작업만으로 돌을 치워야 합니다.

			# '''인접한 두 장소'''에서 '동일한 개수'의 조약돌을 가져가기.
			# '''한 장소'''에서 '임의의 개수'의 조약돌을 모두 가져가기.

			* '''목표:''' 모든 조약돌을 치우는 데 필요한 '''최소 작업 횟수'''를 구해야 합니다. (N <= 2,500)


			=== 💡 문제 풀이 시뮬레이션 ===
			만약 2번 작업(자기 자리를 모두 치우기)만 쓴다면, 모든 돌을 치우는 데 최대 '''N번'''의 작업이 필요합니다.

			그렇다면 우리는 이 N번의 작업에서 횟수를 절약할 수 있는 경우를 찾아 빼줘야 합니다.

			[[파일:2022KOI조약돌1.png]]



			우리가 이 N번의 전체 횟수를 절약할 수 있는 유일한 방법은 바로 이전 장소와 현재 장소의 돌을 짝지어 동시에 치우는 것(1번 작업)뿐입니다.

			하지만 무작정 인접한 돌을 함께 덜어낸다고 해서 무조건 이득이 되는 것은 아닙니다.

			연쇄적으로 돌을 지워나가다가 돌이 애매하게 남아버리면, 결국 누군가가 그 자리에 가서 2번 작업을 또 써야 하기 때문입니다.



			[[파일:2022KOI조약돌2.png]]

			따라서 우리가 찾아야할 상황은 이전 위치와 엮어서 지워나가다가, '''남는 돌 없이 양쪽이 완벽하게 청소되어 횟수가 절약되는 순간'''입니다.

			최대 작업 횟수(N)에서 절약할 수 있는 횟수를 모두 빼면 최소 작업 횟수가 됩니다.


			[[파일:2022KOI조약돌3.png]]

			앞선 그림에서 보았듯, 돌을 완벽하게 치워서 횟수를 절약하려면 연쇄 작용이 딱 맞아떨어져야 합니다.

			"0번부터 묶어볼까? 아니면 0번은 가만히 두고 1번부터 묶어볼까?" 어느 위치에서 연쇄 작용을 시작할지 모든 경우를 따져봐야 합니다.

			이 수많은 경우를 매번 처음부터 다시 계산하면 과정이 너무 복잡해집니다. 따라서 이번에는 '''동적 계획법(DP)'''을 활용해보겠습니다.

			동적 계획법의 핵심은 "미리 계산해 둔 값을 재활용하자"는 것입니다.

			앞에서 힘들게 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하면서 계속 써먹는 방식입니다.

			이전까지 확인하면서 얻어낸 '''가장 많이 절약한 횟수'''를 '''DP 테이블(배열)'''에 적어두고, 이후 단계에서 그 값을 계속 활용할 수 있습니다.


			'''📊 DP 테이블 채우기'''

			예제4 [2, 3, 6, 10, 5]를 통해 DP 테이블 갱신과정을 알아봅시다.

			* 초기 상태: DP = [0, 0, 0, 0, 0] (아직 한 번도 절약하지 못함)

			[[파일:2022KOI조약돌4.png]]



			'''1. 0번 위치에서 제거 시작'''

			* 0번 위치의 돌(2개)부터 시작해 인접한 돌들을 묶어서 연쇄적으로 치워나갑니다.
			* ①, ②, ③ 과정을 거치며 돌이 계속 남지만, 마지막 ④번 위치에서 남는 돌 없이 딱 0개로 정리됩니다.
			* 완벽하게 청소되는 구간을 찾았으므로 1회 절약에 성공했습니다. 이 결과를 4번 인덱스에 기록합니다.

			▶ 갱신된 DP 테이블: DP = [0, 0, 0, 0, 1]


			[[파일:2022KOI조약돌5.png]]

			'''2. 0번 위치를 건너뛰고 1번 위치부터 시작'''

			0, 1번 위치를 동시에 치우지 않고 0번 위치만 먼저 정리한 상황입니다.

			* ①, ② 과정을 거치다가, ③번 과정에서 남은 돌(7개)이 다음 장소의 돌(5개)보다 많아 함께 처리할 수 없게 됩니다. (추가 절약 실패)
			* 절약한 점은 없지만, 앞선 1단계에서 얻어둔 최고 기록(1회 절약)은 날아가지 않고 DP 테이블에 그대로 유지됩니다.

			▶ 갱신된 DP 테이블: DP = [0, 0, 0, 0, 1]



			'''3. 이후'''

			* 이후 2번, 3번, 4번 위치를 새로운 기준점으로 잡아 탐색을 계속해도 추가적인 절약은 발생하지 않습니다.
			* 결국 DP 테이블의 마지막까지 안전하게 전달된 최대 절약 횟수는 1입니다.

			▶ 최소 작업 횟수: 전체 작업 횟수(5) - 최대 절약 횟수(1) = 4번


			=== 💻 코드 구현 ===
			<syntaxhighlight lang="python3" line="1">
			import sys
			input = sys.stdin.readline

			n = int(input())
			rock = list(map(int, input().split()))

			# dp[i]: i번째 장소까지 확인했을 때, 1번 작업을 통해 최대로 절약한 작업 횟수
			dp = [0] * n

			for i in range(n):
			# 이전까지 모아둔 절약 횟수를 그대로 끌고 옴
			if i > 0:
			dp[i] = max(dp[i], dp[i-1])

			x = rock[i]
			# i번째부터 시작해서 이전 돌과 현재 돌을 함께 치워보기
			for j in range(i + 1, n):
			x = rock[j] - x # 다음 장소의 돌 개수에서 이전 돌 개수만큼 덜어냄

			# 돌이 모자라면 이 구간은 완벽히 비울 수 없으므로 탐색 중단
			if x < 0:
			break

			# 남는 돌 없이 딱 0이 떨어지는 완벽한 구간을 찾았다면 작업 횟수 1회 절약
			if x == 0:
			if i > 0:
			p = dp[i-1]
			else:
			p = 0

			# 기존 절약 기록과 이전 누적 절약 횟수 + 이번 1회 절약 중 더 큰 값으로 갱신
			dp[j] = max(dp[j], p + 1)
			break

			# 전체 최악의 작업 횟수(n)에서 최대로 절약한 횟수(dp[-1]를 빼면 최소 작업 횟수
			print(n - dp[-1])
			</syntaxhighlight>

			=== ===

2026년 4월 29일 (수) 10:04에 ArduWiki님의 편집

2026-04-29T10:04:39Z

← 이전 판		2026년 4월 29일 (수) 19:04 판
1번째 줄:		1번째 줄:
	{{#seo:\|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이\|title_mode=append\|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2022 KOI, 2022 초등부 1차 대회 2교시\|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.\|image=https://arduwiki.com/html/resources/assets/arduwiki.png}}		{{#seo:\|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이\|title_mode=append\|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2022 KOI, 2022 초등부 1차 대회 2교시, 빵, 조약돌, 정올 빵, 정올 조약돌\|description=한국정보올림피아드(KOI) 기출 문제 풀이본을 수록합니다.\|image=https://arduwiki.com/html/resources/assets/arduwiki.png}}

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

ArduWiki: /* 1. 빵 (초1) */

2026-04-28T11:47:13Z

1. 빵 (초1)

@@ 8번째 줄: / 8번째 줄: @@
 == '''[https://codersit.co.kr/oj/problems/1369 1. 빵 (초1)]''' ==
 제목 링크를 통해 문제를 확인해주세요.
 == '''[https://codersit.co.kr/oj/problems/1464 2. 조약돌 (초2)]''' ==
 제목 링크를 통해 문제를 확인해주세요.

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

2026-04-28T09:29:15Z

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

새 문서

{{#seo:|title=아두위키 : 한국정보올림피아드(KOI) 기출문제 풀이|title_mode=append|keywords=정보올림피아드, 한국정보올림피아드, KOI, 정올, 정올 1차대회, 정올 2차대회, 사고력, 자료구조, 컴퓨팅 사고력, 프로그래밍 대회, 정올 기출, 2022 KOI, 2022 초등부 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/1369 1. 빵 (초1)]''' ==
제목 링크를 통해 문제를 확인해주세요.

== '''[https://codersit.co.kr/oj/problems/1464 2. 조약돌 (초2)]''' ==
제목 링크를 통해 문제를 확인해주세요.