[도해해설] 조이 2021-2022 1차 예선 1차 문제 4박스와 열쇠.

도해 해설 시리즈

이제 막 경기 프로그램 설계를 시작한 AtCoder의 해설과 JOI의 해설을 아직 완전히 알아듣지 못한 사람을 대상으로 도해를 사용해 해설을 진행한다.

문제문

정보 올림픽 일본 위원회 등재 문제

AtCoder에 게시된 문제

입출력 등 실제 확인 후 자신이 만든 프로그램을 채점할 수 있다.

도해 설명

이번 연도 1차 예선 D문제는 다음 5개 기술을 확인하는 문제다.
1. 입력, 출력을 정확하게 활용
2. 산술 연산자를 정확하게 활용
3. 조건 지점을 정확하게 활용할 수 있다(if)
4. 중복 처리를 적절히 활용
5. 정렬을 정확하게 활용할 수 있다(목록)
문제문을 정리하기 위해 구체적인 숫자를 사용해 그림을 그려 보세요.

입력 예 1을 사용하여 생각하다.보물상자 4개와 M=열쇠 4개가 있습니다.보물상자와 열쇠는 각각 번호가 있고, 보물상자와 열쇠가 같은 번호라면 그 열쇠로 보물상자를 열 수 있다.같은 번호의 보물상자라면 열쇠 하나로 여러 보물상자를 열 수 있다.이럴 때 보물상자를 몇 개 열 수 있을지 고민하는 것이 문제다.

따라서 열쇠를 하나하나 눌러 보물상자를 열 수 있는 열쇠가 있는지 확인하는 방법으로 처리해 보자.변수 cnt를 제작하여 보물상자를 열면 cnt의 값이 1 증가하여 열린 보물상자의 수량을 관리합니다.이 방침에 따라 제작된 절차는 다음과 같다.
d1.py

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
#開けることができた宝箱の数を管理する変数cntを初期値0で作成する
cnt = 0
#宝箱を基準に繰り返し処理をN回実行する
for i in range(N):
  #M個の鍵に対して一つずつ確認を行い、一致するものがあったらcntの値を1増やす
  for j in range(M):
    if A[i]==B[j]:
      cnt = cnt + 1
#変数cntの値を出力して終了
print(cnt)

채점 사이트에 제출하는 프로그램
채점 결과를 보면 WA에 오류가 발생했습니다.왜 이렇게 됐을까?

입력예1을 사용하여 상황을 자세히 살펴보면 마지막 보물상자를 열 때 같은 열쇠가 두 개 있기 때문에 다수가 있다는 것을 알 수 있다.보물상자를 열 수 있다면 열쇠를 찾는 일을 중단할 수 있다면 정확하게 셀 수 있을 것이다.

파이톤에 브레이크라는 명령이 있습니다.이 명령을 사용하면 현재 실행 중인 중복 처리를 중단할 수 있습니다.만약 중복 처리가 두 순환이 중첩된다면, 한 개의 중복 처리만 중단된다.

또한 파이썬에는 조사할 값이 배열에 있는지 확인하는 in 연산자가 있습니다.이번처럼 중복된 값이 있더라도 무의식적으로'가치가 있는지 없는지'를 확인할 수 있다.기술 방법은 해답례인 'in 연산자를 사용하는 프로그램' 을 확인하십시오.

해답 예시

인터럽트 처리 프로그램 기술

d2.py

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
#開けることができた宝箱の数を管理する変数cntを初期値0で作成する
cnt = 0
#宝箱を基準に繰り返し処理をN回実行する
for i in range(N):
  #M個の鍵に対して一つずつ確認を行い、一致するものがあったらcntの値を1増やす
  #同じ番号の鍵があると正しい答えを出すことができないので、鍵を探す作業を中断するためにbreakを実行する
  for j in range(M):
    if A[i]==B[j]:
      cnt = cnt + 1
      break
#変数cntの値を出力して終了
print(cnt)

채점 사이트에 제출하는 프로그램

in 연산자를 사용하는 프로그램

in 연산자를 사용하면 유창한 프로그램이 됩니다.언어의 고유한 기능을 효과적으로 이용함으로써 복잡한 처리를 간단하게 기술할 수 있다.
d3.py

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
#開けることができた宝箱の数を管理する変数cntを初期値0で作成する
cnt = 0
#宝箱を基準に繰り返し処理をN回実行する
for i in range(N):
  #i番目の宝箱に対応する鍵があるかどうかin演算子を使ってチェックする
  #一致する鍵があったら、変数cntの値を1増やす
  if A[i] in B:
    cnt = cnt + 1
#変数cntの値を出力して終了
print(cnt)

채점 사이트에 제출하는 프로그램

삽화

슬라이드에 사용된 아트웍은 모두 "조급한 사람"의 소재입니다.